User's AC Ratio

56.2% (9/16)

Submission's AC Ratio

35.6% (31/87)

Description

有些都市中總是有很多高樓大廈,因此通常會稱為都市叢林。

而你作為一名極限運動員,你想在這些大廈中用滑翔翼穿梭,
使用滑翔翼有個限制,就是只能從高的地方飛向低的地方,
而且你的體力也有限制,所以中途會需要停下來休息。

你現在在某一個都市叢林中,所有大廈都由東向西排成一直線,
你想要從東邊任一棟大廈飛到西邊的任一棟大廈,而且中途要恰休息一次,
於是就想知道有幾種方法能達成。

例如有大廈由東向西的高度依序為 $5,3,4,2,1$
你可以選擇從 $5$ 飛到 $2$ ,中途在 $4$ 休息一次,
也可以選擇從 $4$ 飛到 $1$ ,中途在 $2$ 休息一次。
綜合下來有以下 $7$ 種方法,三個數字分別代表起點大廈、休息大廈、終點大廈:

$5,3,2$
$5,3,1$
$5,4,2$
$5,4,1$
$5,2,1$
$3,2,1$
$4,2,1$

Input Format

第一行有一個正整數 $N\ (3\leq N\leq8\times10^ 5)$ ,代表這個都市叢林的大廈有幾個。
接下來一行有 $N$ 個非負整數,代表由東向西的大廈高度,保證所有大廈高度皆不大於 $10^ 9$ 且高度均不相同。

Output Format

輸出一個正整數,代表題目所述的方法數。

Sample Input 1

5
5 3 4 2 1

Sample Output 1

7

Sample Input 2

9
1 9 4 3 8 5 7 2 6

Sample Output 2

14

Hints

賽後將 $N$ 的範圍加大到 $8\times10^ 5$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~7 $N\leq5\times10^ 2$ 18
2 0~18 $N\leq5\times10^ 3$ 36
3 0~29 無特別限制 46

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 1 2 3
3 1000 65536 65536 1 2 3
4 1000 65536 65536 1 2 3
5 1000 65536 65536 1 2 3
6 1000 65536 65536 1 2 3
7 1000 65536 65536 1 2 3
8 1000 65536 65536 2 3
9 1000 65536 65536 2 3
10 1000 65536 65536 2 3
11 1000 65536 65536 2 3
12 1000 65536 65536 2 3
13 1000 65536 65536 2 3
14 1000 65536 65536 2 3
15 1000 65536 65536 2 3
16 1000 65536 65536 2 3
17 1000 65536 65536 2 3
18 1000 65536 65536 2 3
19 1000 65536 65536 3
20 1000 65536 65536 3
21 1000 65536 65536 3
22 1000 65536 65536 3
23 1000 65536 65536 3
24 1000 65536 65536 3
25 1000 65536 65536 3
26 1000 65536 65536 3
27 1000 65536 65536 3
28 1000 65536 65536 3
29 1000 65536 65536 3