有些都市中總是有很多高樓大廈,因此通常會稱為都市叢林。
而你作為一名極限運動員,你想在這些大廈中用滑翔翼穿梭,
使用滑翔翼有個限制,就是只能從高的地方飛向低的地方,
而且你的體力也有限制,所以中途會需要停下來休息。
你現在在某一個都市叢林中,所有大廈都由東向西排成一直線,
你想要從東邊任一棟大廈飛到西邊的任一棟大廈,而且中途要恰休息一次,
於是就想知道有幾種方法能達成。
例如有大廈由東向西的高度依序為 $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$ |
第一行有一個正整數 $N\ (3\leq N\leq8\times10^ 5)$ ,代表這個都市叢林的大廈有幾個。
接下來一行有 $N$ 個非負整數,代表由東向西的大廈高度,保證所有大廈高度皆不大於 $10^ 9$ 且高度均不相同。
輸出一個正整數,代表題目所述的方法數。
賽後將 $N$ 的範圍加大到 $8\times10^ 5$
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 |