/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。 高橋君は P に対して次の操作を繰り返し(0回でも良い)行う事ができます。
- 1\leq i\leq N-1 をみたす整数を 1 つ選ぶ。コスト i を支払い、P_i と P_{i+1} を交換する。
P を昇順にソートするために必要なコストの総和の最小値を求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- (P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の順列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
P を昇順にソートするために必要なコストの総和の最小値を出力せよ。
入力例 1
3 3 2 1
出力例 1
4
高橋君のは次のようにして P を昇順にソートすることができます。
- コストを 1 支払い、P_1=3 と P_2=2 を交換する。P=(2,3,1) となる。
- コストを 2 支払い、P_2=3 と P_3=1 を交換する。P=(2,1,3) となる。
- コストを 1 支払い、P_1=2 と P_2=1 を交換する。P=(1,2,3) となる。
このように操作を行ったときコストの総和は 4 であり、このときが最小となります。
入力例 2
5 2 4 1 3 5
出力例 2
6
入力例 3
2 1 2
出力例 3
0
Score : 600 points
Problem Statement
You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Takahashi can repeatedly perform the following operation on P (possibly zero times):
- Choose an integer i satisfying 1 \leq i \leq N-1. Pay a cost of i, and swap P_i and P_{i+1}.
Find the minimum total cost required to sort P in ascending order.
Constraints
- 2 \leq N \leq 2 \times 10^5
- (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Print the minimum total cost required to sort P in ascending order.
Sample Input 1
3 3 2 1
Sample Output 1
4
Takahashi can sort P in ascending order as follows:
- Pay a cost of 1 and swap P_1 = 3 and P_2 = 2. Now, P = (2, 3, 1).
- Pay a cost of 2 and swap P_2 = 3 and P_3 = 1. Now, P = (2, 1, 3).
- Pay a cost of 1 and swap P_1 = 2 and P_2 = 1. Now, P = (1, 2, 3).
The total cost for these operations is 4, which is the minimum possible.
Sample Input 2
5 2 4 1 3 5
Sample Output 2
6
Sample Input 3
2 1 2
Sample Output 3
0