Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | consir.in, consir.out | Sursă | Autumn Warmup 2007, Runda 3 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Consir
Vultur a gasit in cartea de chimie o problema care nu stie sa o rezolve si are nevoie de ajutorul vostru. Se da o secventa A, formata din N numere naturale. Un consir este un sir de numere naturale i1, i2 ... ip (cuprinse intre 1 si N) cu proprietatea ca A[i1], A[i2] ... A[ip] sunt numere consecutive. Determinati K, lungimea maxima a unui consir ce se poate forma, precum si numarul de consiruri distincte de lungime 1, 2 ... K.
Date de intrare
Pe prima linie a fisierului consir.in se va afla numarul N avand semnificatia din enunt. Pe urmatoarele N linii se afla valorile secventei A, mai exact pe linia i+1 se afla valoarea lui A[i].
Date de iesire
Pe prima linie a fisierului consir.out se va afla valoarea K, avand semnificatia din enunt. In continuare vor urma K linii, pe linia i+1 aflandu-se numarul de consiruri distincte de lungime i.
Restrictii
- 1 ≤ N ≤ 200 000
- Termenii sirului au valori cuprinse intre 1 si 1 000 000
- Se garanteaza ca fiecare raspuns are o valoare mai mica decat 263 (se incadreaza pe tipuri de date intregi pe 64 biti fara semn)
- Lungimea unui consir este data de numarul de elemente
- Doua consiruri X si Y sunt distincte daca exista o pozitie i astfel inca X[i] diferit de Y[j]
Exemplu
| consir.in | consir.out |
|---|---|
| 6 1 2 1 3 4 5 | 5 6 5 4 3 2 |
Explicatie
...
