Problem A
Duplantis
Languages
en
sv
Duplantis har ett problem. Han kan inte bestämma sig för om han ska slå så många världsrekord som möjligt eller ett världsrekord som är så bra som möjligt.
Just nu är hans världsrekord på $v$ cm. Duplantis har förutspått hur hans form kommer vara de resterande $N$ tävlingarna i karriären, och har räknat fram de positiva heltalen $a_1, a_2, \dots , a_N$. Talet $a_i$ innebär att Duplantis kan hoppa mellan $0$ och $a_i$ cm i den $i$:te tävlingen. Han kan bestämma fritt hur högt han kommer hoppa i en viss tävling, så länge som höjden är ett heltal mellan $0$ och $a_i$ cm.
För att slå ett världsrekord måste Duplantis hoppa strikt högre än sitt förra världsrekord. Det är bara tillåtet att slå som mest ett världsrekord i en och samma tävling. I stavhopp så hoppar man alltid ett helt antal centimeter.
Din uppgift är att räkna fram $r$, det maximala antalet fler världsrekord Duplantis kan slå. Du ska också räkna ut talen $b_1, b_2, \dots , b_r$, där $b_i$ är det maximala möjliga slutgiltiga världsrekordet givet att Duplantis slår exakt $i$ fler världsrekord.
Indata
Den första raden innehåller två heltal $N$ och $v$ ($1 \leq N \leq 3 \cdot 10^5$, $0 \leq v \leq 10^9$), där $N$ är antalet tävlingar och $v$ är Duplantis nuvarande världsrekord.
Den andra raden innehåller $N$ heltal $a_1, a_2, \dots , a_N$ ($0 \leq a_i \leq 10^9$).
Utdata
På den första raden, skriv ut $r$, det maximala antalet fler världsrekord Duplantis kan slå. På den andra raden, skriv ut de $r$ talen $b_1, b_2, \dots , b_r$, där $b_i$ är det maximala möjliga slutgiltiga världsrekordet om Duplantis slår exakt $i$ fler världsrekord.
Notera att $r$ kan vara noll, i så fall ska du lämna den andra raden tom (att inte skriva ut en tom rad är också OK).
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$20$ |
$v < a_1 < a_2 < \dots < a_N$ |
|
$2$ |
$20$ |
$a_1 > a_2 > \dots > a_N$ |
|
$3$ |
$17$ |
$N = 2$ |
|
$4$ |
$43$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I det första exemplet kan Duplantis slå som mest $3$ fler världsrekord. Till exempel kan han hoppa $635$ i första tävlingen, $640$ i andra, och slutligen $650$ i fjärde tävlingen. I resterande tävlingar kan han göra vad som helst. Ifall han bara slår ett världsrekord så kan han uppnå ett högre världsrekord, genom att hoppa $700$ i första tävlingen.
I det andra exemplet verkar det tyvärr som att Duplantis redan har uppnått sin topp, och kan då inte slå några fler världsrekord.
| Exempel på indata 1 | Exempel på utdata 1 |
|---|---|
6 630 700 645 620 650 631 100 |
3 700 650 650 |
| Exempel på indata 2 | Exempel på utdata 2 |
|---|---|
3 630 630 610 580 |
0 |
