28505번 - Niz 서브태스크다국어

문제

Zadan je niz od $N$ prirodnih brojeva $a_i$ (1ドル ≤ a_i ≤ N$).

Koliko postoji parova brojeva $l$ i $r$ (1ドル ≤ l ≤ r ≤ N$) takvih da je uzastopni podniz od $l$-te do $r$-te pozicije permutacija brojeva od 1ドル$ do $r - l + 1$?

입력

U prvom je retku prirodni broj $N,ドル duljina danog niza.

U drugom su retku brojevi $a_1, a_2, \dots , a_N,ドル redom vrijednosti niza. Vrijedi 1ドル ≤ a_i ≤ N$ za sve $i = 1, 2, \dots , N$.

출력

U jedini redak ispišite traženi broj podnizova koji čine permutaciju navedenog oblika.

제한

• 1ドル ≤ N ≤ 10^6$

서브태스크

힌트

Pojašnjenje trećeg probnog primjera:

Parovi $(l, r)$ koji određuju podniz koji je permutacija su:

• $(l, r) = (2, 2)$: 1ドル$
• $(l, r) = (1, 2)$: 2,ドル 1$
• $(l, r) = (1, 3)$: 2,ドル 1, 3$
• $(l, r) = (4, 4)$: 1ドル$
• $(l, r) = (4, 5)$: 1,ドル 2$
• $(l, r) = (4, 6)$: 1,ドル 2, 3$
• $(l, r) = (4, 7)$: 1,ドル 2, 3, 4$
• $(l, r) = (3, 5)$: 3,ドル 1, 2$