Lumanari6

Cerință

Într-o seară de toamnă, $n$ lumânări sunt așezate în linie pe un pervaz, fiecare având o înălțime exprimată printr-un număr natural. Vine un vânt puternic care bate în mai multe runde, alternând direcția. În prima rundă, vântul bate dinspre stânga spre dreapta. O lumânare se stinge dacă înălțimea ei este strict mai mică decât înălțimea primului vecin aprins din stânga ei. Toate stingerile dintr-o rundă au loc simultan.

În a doua rundă, vântul bate dinspre dreapta spre stânga. Dintre lumânările rămase aprinse la runda anterioară, se stinge orice lumânare a cărei înălțime este strict mai mică decât înălțimea primului vecin aprins din dreapta sa. Toate stingerile de la o rundă au loc simultan.

Micul Gates dorește să afle:

1. câte lumânări rămân aprinse după primele două runde și care sunt pozițiile acestora.
2. numărul de runde în care cel puțin o lumânare s-a stins, dacă vântul continuă să bată alternativ (stânga, dreapta, stânga, dreapta, ...) până când, la o rundă completă nu mai stinge nicio lumânare.

Date de intrare

Fișierul de intrare lumanari.in conține: pe prima linie, numărul natural $c$ ($1$ sau $2$) - cerința de rezolvat, pe a doua linie, numărul natural $n$ - numărul de lumânări, pe a treia linie, $n$ numere naturale separate printr-un spațiu reprezentând înălțimile lumânărilor, în ordinea poziției lor de la stânga la dreapta.

Date de ieșire

Fișierul de ieșire lumanari.out va conține:

• Dacă $c = 1$: pe prima linie numărul de lumânări rămase aprinse, apoi pozițiile lor (câte una pe linie, în ordine crescătoare);
• Dacă $c = 2$: o singură linie conținând numărul de runde în care cel puțin o lumânare s-a stins.

Restricții și precizări

• $2 ≤ n ≤ 10 \ 000$
• Înălțimile lumânărilor sunt numere naturale cu valori între $1$ și $100 \ 000$
• Prima lumânare aprinsă din stânga nu are vecin aprins la stânga și nu se poate stinge într-o rundă de stânga
• Ultima lumânare aprinsă din dreapta nu are vecin aprins la dreapta și nu se poate stinge într-o rundă de dreapta

Exemplul 1

lumanari.in

1
7
4 2 5 3 6 6 1

lumanari.out

2
5
6

Explicație

După runda $1$ (vânt din stânga), se sting lumânările de la pozițiile $2$, $4$ și $7$, deoarece:

• $v[2] = 2 < v[1] = 4$
• $v[4] = 3 < v[3] = 5$
• $v[7] = 1 < v[6] = 6$

Rămân aprinse pozițiile: $1$, $3$, $5$, $6$.

După runda $2$ (vânt din dreapta), dintre lumânările rămase aprinse:

• lumânarea de la poziția $3$ ($h=5$) are primul vecin aprins din dreapta la poziția $5$ ($h=6$): $5 < 6$, se stinge
• lumânarea de la poziția $1$ ($h=4$) are primul vecin aprins din dreapta la poziția $3$ ($h=5$): $4 < 5$, se stinge
• lumânările de la pozițiile $5$ și $6$ rămân aprinse

Exemplul 2

lumanari.in

2
7
4 2 5 3 6 6 1

lumanari.out

2

Explicație

Runda $1$ (stânga): se sting lumânările de pe pozițiile: $2$, $4$ și $7$. Rămân: $1$, $3$, $5$, $6$.
Runda $2$ (dreapta): se sting lumânările de la pozițiile: $1$, $3$. Rămân: $5$, $6$.
Runda $3$ (stânga): nu se mai stige nicio lumînare.
Total runde cu stingeri: $2$. Runda $3$ nu a stins nicio lumânare — procesul se oprește și nu se numără.