409034: GYM103423 A Bordered Subarrays

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.

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$$$).

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

• 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.

5
1 2 4 3 5

11

8
2 1 6 3 6 7 8 5

18

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]$$$.