CF1175F.The Number of Subpermutations

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You have an array $a_1, a_2, \dots, a_n$ .

Let's call some subarray $a_l, a_{l + 1}, \dots , a_r$ of this array a subpermutation if it contains all integers from $1$ to $r-l+1$ exactly once. For example, array $a = [2, 2, 1, 3, 2, 3, 1]$ contains $6$ subarrays which are subpermutations: $[a_2 \dots a_3]$ , $[a_2 \dots a_4]$ , $[a_3 \dots a_3]$ , $[a_3 \dots a_5]$ , $[a_5 \dots a_7]$ , $[a_7 \dots a_7]$ .

You are asked to calculate the number of subpermutations.

输入格式

The first line contains one integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ).

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ( $1 \le a_i \le n$ ).

This array can contain the same integers.

输出格式

Print the number of subpermutations of the array $a$ .

输入输出样例

输入#1
```
8
2 4 1 3 4 2 1 2
```
输出#1
```
7
```
输入#2
```
5
1 1 2 1 2
```
输出#2
```
6
```

说明/提示

There are $7$ subpermutations in the first test case. Their segments of indices are $[1, 4]$ , $[3, 3]$ , $[3, 6]$ , $[4, 7]$ , $[6, 7]$ , $[7, 7]$ and $[7, 8]$ .

In the second test case $6$ subpermutations exist: $[1, 1]$ , $[2, 2]$ , $[2, 3]$ , $[3, 4]$ , $[4, 4]$ and $[4, 5]$ .

首页