Din mulţimea permutărilor de ordinul n se alege submulţimea formată din permutările care au proprietatea: începând cu poziţia a doua, fiecare termen al permutării este fie mai mare, fie mai mic decât toţi termenii precedenţi.
Cerinţă
Considerând această submulţime ordonată lexicografic, scrieţi un program care citeşte o permutare de ordin n care are proprietatea din enunţ şi determină numărul de ordine al permutării.
Date de intrare
Fişierul de intrare nrperm.in conţine pe prima linie numărul natural n, iar pe linia a doua n numere naturale care reprezintă termenii unei permutări cu proprietatea din enunţ, termenii fiind separaţi prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire nrperm.out va conţine o singură linie pe care va fi scris numărul de ordine al permutării.
Restricţii
4 <= n <= 64
Exemple
nrperm.in
nrperm.out
Explicaţie
nrperm.in
nrperm.out
Explicaţie
4
2 1 3 4
2
Permutările de ordin 4 cu proprietatea din enunţ în ordine lexicografică sunt: 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321
5
3 4 2 5 1
10
Permutările de ordin 5 cu proprietatea din enunţ în ordine lexicografică sunt: 12345, 21345, 23145, 23415, 23451, 32145, 32415, 32451, 34215, 34251, 34521, 43215, 43251, 43521, 45321, 54321