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 pe 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 i₁, i₂ ... i_p (cu valori cuprinse intre 1 si N) cu proprietatea ca A[i₁], A[i₂] ... A[i_p] sunt numere consecutive. Mai exact A[i₂]=A[i₁]+1, A[i₃]=A[i₂]+1 ... A[i_p]=A[i_p-1]+1. 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 ≤ 310 000
• Termenii sirului au valori cuprinse intre 1 si 1 000 000
• Se garanteaza ca fiecare raspuns are o valoare mai mica decat 2⁶³ (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 incat X_i diferit de Y_i
• In cel putin 30% din teste N ≤ 1000

Exemplu

Explicatie

Cele 2 consiruri de lungime 5 sunt 1 2 4 5 6 si 3 2 4 5 6
Cele 3 consiruri de lungime 4: 1 2 4 5, 3 2 4 5 si 2 4 5 6
Cele 4 consiruri de lungime 3: 1 2 4, 2 4 5, 3 2 4 si 4 5 6
Cele 5 consiruri de lungime 2: 1 2, 2 4, 4 5, 3 2 si 5 6
Cele 6 consiruri de lungime 1: 1, 2, 3, 4, 5 si 6

Cum se trimit solutii?