TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

92.9% (26/28)

Submission's AC Ratio

44.4% (40/90)

Tags

Description

某日,鄉下人要去FN家愉快地玩耍,卻發現FN睡死在家裡了。

然而頑強的鄉下人並不想要因此而露宿街頭,他很快的打電話給檸檬求救,但檸檬的記性很不好,只能大概列出可能是FN家的地點的優先順序

鄉下人想知道,在最糟糕的情況下,自己究竟要多久才能找到FN的家?

數字為優先順序!數字為優先順序!數字為優先順序! (很重要所以講三次!)

Input Format

$n$

$s_1\ s_2\ ...\ s_n$

第一行只有一個數字$n(1 \le n \le 5 \times 10^6)$代表可能是FN家的地點數量,

第二行有$n$個數字$s_i(1 \le i \le n, 1 \le s_i \le n)$代表位置為$i$的地點可能是FN家的優先順序(由小到大),當 $i$ ≠ $j$,$s_i$ ≠ $s_j$。

鄉下人初始的位置為$0$,對任兩個位置$i, j$其距離為$|i - j|$。

鄉下人需要依照$s_i$由小到大依序尋訪,不能偷吃步(即每次尋訪要先走到目前尚未走過的地點中,$s_i$為最小的地點)。

Output Format

輸出一個數字代表鄉下人最多需要走多遠。

Sample Input 1

3
1 3 2

Sample Output 1

4

Sample Input 2

5
1 3 5 2 4

Sample Output 2

11

Sample Input 3

7
6 5 7 2 4 3 1

Sample Output 3

19

Hints

以範測1為例:

鄉下人原本的位置為0

$s_1 = 1$,位置0 => 1

$s_3 = 2$,位置1 => 3

$s_2 = 3$,位置3 => 2

總距離$|1 - 0|+ |3 - 1| + |2 - 3| = 4$

如果你用c++ 的 cin 一直吃TLE的話
可以在main函數裡面新增一行
ios_base::sync_with_stdio(false);cin.tie(0);
這叫做io優化喔 在資料量大的時候可以大幅縮短執行時間

Problem Source

Subtasks

No. Testdata Range Score
1 0~6 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536 1
1 1000 250000 250000 65536 1
2 1000 250000 250000 65536 1
3 1000 250000 250000 65536 1
4 1000 250000 250000 65536 1
5 1000 250000 250000 65536 1
6 1000 250000 250000 65536 1