Niz

시간 제한1초메모리 제한1024 MB

요약

값이 10^6까지인 배열에서 길이만큼의 1부터 그 길이까지의 순열이 되는 부분 배열의 개수를 센다.

난이도: 보통10점 중 7점
유형: 배열, 해시맵, 누적 합
정답자: 아직 제출이 없습니다

문제

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$

예제3

예제 1
입력
```
3
3 1 2
```
예상 출력
```
3
```
예제 2
입력
```
5
3 2 1 2 3
```
예상 출력
```
5
```
예제 3
입력
```
7
2 1 3 1 2 3 4
```
예상 출력
```
8
```