409034: GYM103423 A Bordered Subarrays

Memory Limit:128 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Bordered Subarraystime limit per test0.7 secondsmemory limit per test128 megabytesinputstandard inputoutputstandard 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.
ExamplesInput
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]$$$.

加入题单

上一题 下一题 算法标签: