c020. 202010_4. 低地距離

Content

輸入一個長度為 $2n$ 的陣列，其中 $1$ ~ $n$ 的每個數字都剛好各 2 次。

$i$ 的低窪值的定義是兩個數值為 $i$ 的位置中間，有幾個小於 $i$ 的的數字。

以 $[3, 1, 2, 1, 3, 2]$ 為例，1 的低窪值為 0, 2 的低窪值值為 1, 3 的低窪值為 3。

請對於每個 $1 \sim n$ 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。

Input

第一行有一個正整數 $n$

第二行有 $2n$ 個正整數，以空格分隔，保證 $1 \sim n$ 每個數字都恰好出現兩次。

配分

20%: $1\leq n \leq 1000$
40%: $1\leq n \leq 40000$
40%: $1\leq n \leq 100000$

Output

輸出 $1$ ~ $n$ 每個數字的低窪值總和。

Sample Input #1

3
3 1 2 1 3 2

Sample Output #1

測資資訊：

記憶體限制： 250 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <10M
公開測資點#8 (10%): 1.0s , <10M
公開測資點#9 (10%): 1.0s , <10M

Hint ：

Tags:

出處:

2020年10月APCS 演算法海牛 [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」