Soluții trimise

Considerând K un număr natural, vom numi permutare de mărime K o aranjare într-o ordine oarecare a elementelor mulțimii {1,2,..,K}. Ana găsește scris pe o foaie de hârtie, un șir de numere naturale v = (v[1],v[2],v[3],...,v[N])

Plecând de la acest șir, Ana numește secvență a lui v, un subșir de numere care apar pe poziții consecutive în șirul inițial. De exemplu, șirul 5 7 8 9 1 6 conține secvența 8 9 1, secvența 7 8 9 1 6, dar nu conține secvența 8 9 6.

Anei îi vine ideea să încerce să verifice dacă șirul de numere poate fi împărțit în secvențe care reprezintă permutări de diferite mărimi.

De exemplu, dacă Ana găsește șirul v =(2, 1, 4, 1, 3, 2), atunci ea îl poate împărți în două secvențe de permutări astfel: secvența v[1], v[2] respectiv secvența v[3] , v[4], v[5], v[6].

Dacă Ana găsește șirul v =( 1, 2, 2, 3) atunci nu va putea obține o împărțire în secvențe de permutări.

Realizați un program care citește un șir de N numere naturale și rezolvă următoarea cerință:

• determină o împărțire a acestuia în secvențe de permutări. Dacă există mai multe soluții se va afișa soluția minim lexicografică.

Dacă șirul poate fi împărțit în secvențe de permutări, pentru fiecare număr din șir, în ordinea v[1], .., v[N], se va afișa numărul permutării din care face parte.

Numerotarea permutărilor se va face consecutiv începând cu numărul 1.