Cerința

O permutare de ordin K este formată din toate numerele 1, 2, …, K nu neapărat în această ordine.
O secvență de lungime L este formată din L elemente ale șirului aflate pe poziții consecutive. Spunem că o secvență de lungime L este permutare de ordin L dacă ea conține toate numerele 1, 2, …, L, nu neapărat în această ordine.

Se dă un șir de N numere naturale nenule \( {a}_{1}, {a}_{2}, …,{a}_{N} \), ce reprezintă o permutare de ordin N. Să se calculeze numărul secvențelor din șirul a care au proprietatea că sunt permutări.

Date de intrare

Fișierul de intrare permutari4.in conține pe prima linie numărul natural N, iar pe a doua linie se află primele N numere naturale nenule, separate prin spațiu. Cele N numere date nu sunt obligatoriu în ordine strict crescătoare.

Date de ieșire

În fișierul de ieșire permutari4.out se va scrie un singur număr natural reprezentând numărul secvențelor de tip permutare care apar în şirul dat.

Restricții și precizări

• 1 < N ≤ 100.000

Exemplu:

permutari4.in

7
4 2 5 1 3 7 6

permutari4.out

3

Explicație

În şir există 3 secvențe de tip permutare, de lungimi 1, 5 şi 7:
1
4 2 5 1 3
4 2 5 1 3 7 6
Nu există secvențe permutare de lungime 2, 3, 4 sau 6.