Toată lumea cunoaşte celebrele păpuşi de lemn, care încap una în alta, numite matrioşca.
La atelierul unde se confecţionează aceste păpuşi lucrează mai mulţi meşteri, fiecare meşter lucrând numai păpuşi de aceiaşi înălţime. Fiecare meşter, cum termină o păpuşă o aşează pe o bandă rulantă, care duce păpuşile spre secţia de împachetare. Aici lucrează numai Gigel, care ia fiecare păpuşă, în ordinea în care le aduce banda rulantă, şi o aşează fie în una din păpuşile deja sosite, dacă este posibil, fie separat, dacă acest lucru nu este posibil. O păpuşă poate fi introdusă în alta doar dacă înălţimea primeia este strict mai mică decât a celei de a doua.
Cerinţă
Să se determine numărul minim de seturi de păpuşi pe care Gigel le poate forma în procesul de împachetare.
Date de intrare
Prima linie a fişierului de intrare matriosca.in conţine un singur număr natural n, reprezentând numărul păpuşilor de pe banda rulantă. Următoarele n linii conţin fiecare câte un număr natural, reprezentând înălţimile păpuşilor, în ordinea sosirii lor pe bandă la secţia de împachetare.
Date de ieşire
Pe prima linie a fişierului de ieşire matriosca.out se va scrie numărul nrm de seturi de păpuşi împachetate. Următoarele nrm linii vor conţine, fiecare, numărul de păpuşi din setul respectiv, urmat de numerele de ordine ale păpuşilor pe care Gigel le-a pus în set, în ordinea sosirii lor pe bandă.
Restricţii
0<n<2501
înălţimile păpuşilor sunt numere naturale strict pozitive < 2000000000
Exemplu
matriosca.in
matriosca.out
Explicaţii
10
4
1
5
10
7
9
2
8
3
2
4
2 1 2
2 3 7
4 4 5 9 10
2 6 8
Pot fi formate 4 seturi de păpuşi matrioşca:
setul 1: din 2 păpuşi: 1 şi 2
setul 2: din 2 păpuşi: 3 şi 7
setul 3: din 4 păpuşi: 4,5,9 şi 10
setul 4: din 2 păpuşi: 6 şi 8
O altă soluţie posibilă: 4
2 1 2
3 3 9 10
3 4 5 7
2 6 8
