746 . 糕點的高點
Description
每十年一次，來自世界各地頂尖的糕點師傅都會到東京的富士山來比劃自己的糕點程度，想要奪得「天下第一」的名號。在富士山上，有 $N$ 個糕點排成一排，會由來自當地的糕點師傅柳德 政男（りゅうめぐむ まさお）主持評分，將第 $i$ 個糕點給 $x_i$ 分。接下來，他會隨機選擇兩個數字 $l,r \ (1 \leq l \leq r \leq N)$，並且從編號 $l$ 的糕點看到編號 $r$ 的糕點。如果這些糕點內，有一個糕點的評分是嚴格高於區間內的所有其他糕點的評分的話，那這個糕點就會被選為「高點糕點」。
請問有幾個選擇 $l,r$ 的方法使得這個區間有辦法選出一個「高點糕點」？
Input Format
輸出將有兩行。第一行有一個正整數 $N(1 \leq N \leq 10^ 5)$ 代表有幾個糕點。第二行有 $N$ 個數字，第 $i$ 個數字代表給第 $i$ 個糕點的評分 $x_i(1 \leq x_i \leq 10^ 9)$。
Output Format
請輸出一個數字，代表有幾個區間有辦法找出「高點糕點」。
Sample Input 1
5 1 2 3 4 5
Sample Output 1
15
Sample Input 2
6 1 1 1 1 1 2
Sample Output 2
11
Sample Input 3
15 7 9 2 4 7 10 9 1 1 2 3 4 8 9 8
Sample Output 3
117
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~20 | 無額外限制 | 100 |