There are \(n\) buildings in Nandini Society. These buildings are in a straight line with each building having a height \(h_i(1 \leq i \leq n)\) . On the top of each building there is a party going on although it is not allowed.

    In case of any danger a person from a building will make a fire on the top. One person could see the signal of another person, if on the straight line connecting the top of two buildings there was no building higher than any of the two.  For example, for any two neighbouring buildings it is true that the signal of one will be seen by the other.

        You have to find the amount of pairs of person able to see each other's fire signal.

Input

The first line of the input data contains an integer number \(n\) — the amount of buildings in the society. The second line contains \(n\) numbers \(h_i(1 \leq i \leq n)\)— heights of the hills. All height numbers are integer.

Output

Print the required amount of pairs.

Constraints

\(3 \leq n \leq 10^6\)

\(1 \leq h_i \leq 10^9\)