3. Dole kopcom

Dušan je vášnivý turista. Pri svojej poslednej návšteve Vysokých Tatier sa rozhodol písať si denník. Po každom kilometri si zapíše, či išiel hore alebo dole kopcom jeden výškový meter. Dušanovi však zmokol batoh a niektoré zápisky niesú čitateľné. Po príchode domov chcel svojím kamarátom ukázať, kde jedol fajnový obed. Pamätal si, že obed jedol na najvyššom kopci. Avšak kvôli nekompletným záznamom si nie je istý, kde to naozaj bolo. Pomôž mu zistiť koľko takýchto miest mohlo cestou byť.

Úloha

Pre jednoduchosť môže predpokladať stúpanie + a klesanie - za konštantné, posunieme sa hore alebo dole vždy o tú istú hodnotu. ?, znamená, že z poznámok nie je jasné kam sa Dušan posunul ale určite vieme povedať, že išiel buď dole alebo hore – nikdy neostal na tej istej výške. Chceme zistiť koľko kopcov mohlo byť tými najvyššími, a ktoré to mohli byť.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet zápiskov.

Na druhom riadku sa nachádza \(n\) zápiskov (+, -, ?), označujúcich Dušanov pohyb hore a dole. ? znamená, že nevieme určiť, či Dušan išiel hore alebo dole.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš dva riadky. V prvom jedno celé číslo, ktoré hovorí, na koľkých pozíciach sa mohol nachádzať najvyšší kopec Dušanovej cesty. Na druhý riadok napíš pozície, na ktorých sa tieto kopce mohli nachádzať. Na poradí vypísaných pozícií nezáleží.

Príklady

Input:

2
?-

Output:

2
0 1

Vrchol môže byť na 0., kde stál pred tým ako sa pohol. Alebo na 1. pozícii. Ak by sa Dušan najprv posunul dole kopcom (? -> -) tak ak začíname vo výške 0, by mohol stáť vo výškach 0, -1, -2. Ak by sa Dušan najprv posunul hore kopcom (? -> +) tak ak začíname vo výške 0, by mohol stáť vo výškach 0, 1, 0 .

Input:

6
+??-+-

Output:

4
1 2 3 5

Rozoberme si postupne všetky možnosti:

• +++-+- -> 0, 1, 2, 3, 2, 3, 2
• +---+- -> 0, 1, 0,-1,-2,-1,-2
• +-+-+- -> 0, 1, 0, 1, 0, 1, 0
• ++--+- -> 0, 1, 2, 1, 0, 1, 0

Najvyššie miesto cesty môže byť na 1., 2., 3. alebo 5. pozícii. V prvom prípade by najvyšší kopec bol ten na tretej pozícii a piatej pozícii. V druhom prípade by to bol iba ten na prvej pozícii. v treťom prípade by to bol ten na prvej, tretej a piatej pozícii a v poslednom prípade by to bol kopec na druhej pozícii.