Description

You are about to debut.

Your coach and classmates have contacted a photographer for you, and you come to take promotional photos by Des Voeux Road.

There are $n$ buildings on the street, arranged in a line from left to right, numbered from $1$ to $n$. The height of building $i$ is $a_i$.

A photo can be described by an ordered pair $(l,r)$, where $1\le l\le r\le n$. This photo contains all buildings with indices in $[l,r]$.

The photographer thinks a photo is beautiful if and only if it satisfies both conditions below:

• For any $i<j<k$, if buildings of heights $i$ and $k$ both appear in the photo, then buildings of height $j$ also appear in the photo.
• For any $i$, buildings of height $i$ either do not appear in the photo, or appear exactly $i$ times in the photo.

The photographer asks you: how many different beautiful photos can be taken in total?

Two photos $(l_1,r_1)$ and $(l_2,r_2)$ are different if and only if $l_1\ne l_2$ or $r_1\ne r_2$.

Input Format

The first line contains a positive integer $n$, representing the number of buildings.

The next line contains $n$ positive integers. The $i$-th integer is the height of building $i$.

Output Format

Output one line containing one integer, representing the number of different beautiful photos that can be taken.

10
2 2 1 1 2 2 3 1 3 3 

8

Hint

This problem uses bundled tests. You can get the score for a subtask only if you pass all test points in that subtask.

• Subtask 1 (10 points): $n\le 200$.
• Subtask 2 (5 points): $n\le 1000$.
• Subtask 3 (10 points): $n\le 6000$.
• Subtask 4 (20 points): $n\le 3\times 10^4$.
• Subtask 5 (30 points): $n\le 10^5$.
• Subtask 6 (25 points): $n\le 10^6$.

For all testdata: $1\le n,a_i\le 10^6$.

Note that the answer may exceed the range of a $32$-bit signed integer.

The input size is large, so please use a fast input method.

Translated by ChatGPT 5