Una din cele mai noi pasiuni ale lui Zăhărel este să studieze diverse proprietăţi ale permutărilor. De exemplu, este interesat de permutările în care cel mai lung subşir crescător şi cel mai lung subşir descrescător au lungimi date.
Cerinţă
Să se scrie un program care determină o permutare de lungime N în care cel mai lung subşir crescător are lungime A şi cel mai lung subşir descrescător are lungime B.
Date de intrare
Fişierul de intrare ab2.in va conţine pe prima linie numerele N A B.
Date de ieşire
Fişierul de ieşire ab2.out va conţine pe prima linie N numere separate prin câte un spaţiu, reprezentând o permutare care respectă condiţiile de mai sus. Dacă există mai multe soluţii, se va afişa cea minimă din punct de vedere lexicografic.
Restricţii
1 ≤ N,A,B ≤ 30.000
Se garantează că mereu există soluţie pentru datele de intrare
Se numeşte subşir al şirului X=(x1,x2...xN), un şir Y=(xi1,xi2...xiM) cu proprietatea 1≤i1<i2<...<iM≤N
Un şir (x1,x2...xK) este mai mic din punct de vedere lexicografic decat un alt şir (y1,y2...yK) dacă există o poziţie p≤K, astfel încat xp<yp si x1=y1, x2=y2 ... xp-1=yp-1
Pentru un test se va acorda 70% din punctaj dacă permutarea afişată are cel mai lung subşir crescător de lungime A şi cel mai lung subşir descrescător de lungime B, dar nu este minimă lexicografic.
Exemple
ab2.in
ab2.out
Explicaţii
4 2 3
1 4 3 2
Cel mai lung subşir crescător are lungime 2 (1 4, 1 3 sau 1 2), iar cel mai lung subşir descrescător are lungime 3 (4 3 2).
O altă soluţie posibilă este 2 4 3 1, dar aceasta nu este minimă din punct de vedere lexicografic.