시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB213321.429%

문제

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$

서브태스크

번호배점제한
113

Svaki broj od $1$ do $N$ se pojavljuje točno jednom u nizu.

220

$N ≤ 5000$

333

$N ≤ 50000$

434

Nema dodatnih ograničenja.

예제 입력 1

3
3 1 2

예제 출력 1

3

예제 입력 2

5
3 2 1 2 3

예제 출력 2

5

예제 입력 3

7
2 1 3 1 2 3 4

예제 출력 3

8

힌트

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$

채점 및 기타 정보

  • 예제는 채점하지 않는다.