The Number of Subpermutations
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
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$.
Input
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.
Output
Print the number of subpermutations of the array $a$.
8
2 4 1 3 4 2 1 2
5
1 1 2 1 2
7
6
Note
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]$.
20240326集训
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2024-3-26 19:00
- End at
- 2024-3-26 21:00
- Duration
- 2 hour(s)
- Host
-
SamuelXuch
- Partic.
- 14