H. Mexican Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. Count the number of non-empty subarrays$$$^{[1]}$$$ ($$$a[l, l + 1, \ldots, r]$$$) such that its sum is equal to its MEX$$$^{[10]}$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output

Output one line containing a single integer — the number of non-empty subarrays such that their sum is equal to their MEX.

Example
Input
7
1 0 2 0 3 4 3
Output
2