Gigel doreşte să genereze toate subşirurile strict crescătoare ale unui şir cu n elemente.
A şi scris pe foaie un şir cu 8 elemente: (28 2 46 43 44 8 19 15), a observat că cel mai lung subşir crescător are lungimea 3, şi s-a apucat să le noteze pe toate: 2 8 15 (a2, a6, a8)
2 8 19 (a2, a6, a7)
2 43 44 (a2, a4, a5)
28 43 44 (a1, a4, a5)
După cum se vede, aceste subşiruri sunt în ordine lexicografică după valorile lor, dar el ar dori să le scrie în ordine lexicografică după poziţiile elementelor.
Cerinţă
Scrieţi un program care pentru un şir cu n elemente să tipărească toate subşirurile crescătoare de lungime maximă pe câte o linie, elementele fiind identificate prin poziţiile lor, iar soluţiile să fie scrise în ordine lexicografică după acest poziţii.
Date de intrare
Fişierul de intrare sirmax.in
conţine pe prima linie numărul natural n, iar pe linia următoare n numere naturale separate prin spaţiu.
Date de ieşire
Fişierul de ieşire sirmax.out
va conţine pe câte o linie indicii elementelor subşirurilor crescătoare de lungime maximă, scrise în ordine lexicografică.
Restricţii
1 <= n <= 100
elementele şirului sunt pozitive şi nu depăşesc 32000
numărul soluţiilor în niciun caz nu va depăşi 1000.
Exemplu
sirmax.in
sirmax.out
Explicaţie
8
28 2 46 43 44 8 19 15
1 4 5
2 4 5
2 6 7
2 6 8
Avem 4 subşiruri crescătoare de lungime maximă. Indicii subşirurilor sunt în ordine lexicografică. (a1,a4,a5)=(28 43 44)
(a2,a4,a5)=(2 43 44)
(a2,a6,a7)=(2 8 19)
(a2,a6,a8)=(2 8 15)