A. Bordered Subarrays
time limit per test
0.7 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Due to the large input size it is recommended to use an efficient reader.

An array $$$a_1,a_2, \ldots a_n$$$ of $$$n \ge 1$$$ integers is bordered if all of its elements belong to the interval determined by $$$a_1$$$ and $$$a_n$$$.

More exactly, $$$a$$$ is bordered if $$$a_1 \le a_i \le a_n$$$, $$$\forall i \in [1,n]$$$. Therefore, any array of $$$n \le 2$$$ elements is bordered if $$$a_1 \le a_n$$$.

For example, $$$[1]$$$, $$$[1,1]$$$, $$$[3,4,3,4]$$$ and $$$[1,3,2,4]$$$ are bordered arrays, while $$$[\varnothing]$$$, $$$[2,3,1]$$$ and $$$[2,1,4,3]$$$ are not.

For a given array $$$a=[a_1,a_2, \ldots, a_n]$$$, find how many of its subarrays are bordered.

Input

The first line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the number of elements of $$$a$$$. The second line of input contains $$$n$$$ space separated integers, the elements of array $$$a$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Print one integer, the number of bordered subarrays of $$$a$$$.

Scoring
  • Subtask 1 (10 points): $$$1 \le n \le 300$$$;
  • Subtask 2 (15 points): $$$1 \le n \le 10^5$$$, $$$1 \le a_i \le 2$$$;
  • Subtask 3 (20 points): $$$300 \lt n \le 5000$$$;
  • Subtask 4 (30 points): $$$5000 \lt n \le 10^5$$$;
  • Subtask 5 (25 points): No further constraints.
Examples
Input
5
1 2 4 3 5
Output
11
Input
8
2 1 6 3 6 7 8 5
Output
18
Note

In the first sample, the $$$11$$$ bordered subarrays are $$$[1]$$$, $$$[2]$$$, $$$[4]$$$, $$$[3]$$$, $$$[5]$$$, $$$[1,2]$$$, $$$[2,4]$$$, $$$[3,5]$$$, $$$[1,2,4]$$$, $$$[2,4,3,5]$$$ and $$$[1,2,4,3,5]$$$.