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

prof. Ilie Vieru

Colegiul Naţional "Gheorghe Vrînceanu" Bacău

ilie_vieru@yahoo.com