TopCoder

asuka
酸欠少女

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

57.9% (11/19)

Tags

Description

在一座戒備森嚴的碉堡中,有 N 組每組 2 人的士兵在守衛,其中第 i 組士兵能力值排名第 i。碉堡的兩邊都有可能被攻擊,因此理想狀況下,一個穩定的碉堡防禦應該讓能力最強的人在內側,也就是排成 N,N1,,2,1,1,2,,N1,N

根據這個理論,將軍把每個士兵的穩定值定義為有多少組排名比自己大的士兵兩人在自己的異側,而碉堡防禦值為所有士兵的穩定值總和。例如:三組士兵排成 1,3,2,3,1,2,他們穩定值分別為 0,0,1,0,1,0,因此雕堡防禦值為 2

現在給一個士兵的排列,請你回答碉堡防禦值為和?

Input Format

輸入第一行是一個整數 N,表示有多少組士兵。

輸入第二行是 2N 個以空白分隔的整數 ai,依序代表整排士兵的能力值排名。

輸入保證 1aiN,且每個數字恰出現兩次。

對於 20% 的測資,保證 N1000
對於剩下 40% 的測資,保證 N40000
對於剩下 40% 的測資,保證 N100000

Output Format

輸出一行一個整數代表雕堡防禦值。

Sample Input 1

3
1 3 2 3 1 2

Sample Output 1

2

Sample Input 2

4
3 2 4 4 1 1 2 3

Sample Output 2

6

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 1N100 20
3 0~16 1N40000 40
4 0~23 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4
1 2000 524288 65536 1 2 3 4
2 2000 524288 65536 2 3 4
3 2000 524288 65536 2 3 4
4 2000 524288 65536 2 3 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 2 3 4
10 2000 524288 65536 2 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 4
18 2000 524288 65536 4
19 2000 524288 65536 4
20 2000 524288 65536 4
21 2000 524288 65536 4
22 2000 524288 65536 4
23 2000 524288 65536 4