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

Sample Input 2

9
1 9 4 3 8 5 7 2 6

Sample Output 2

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

Submit

Status

Ranklist

28 . 都市滑翔