Mock CCC '18 Contest 5 J4/S2 - Reverse Sort

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

Given a permutation of the first NN positive integers and the ability to swap any two adjacent integers, compute the minimum number of swaps needed to sort the list in decreasing order.

Constraints

1 \le N \le 10^31 \le N \le 10^3

v_iv_i form a permutation of the first NN positive integers.

Input Specification

The first line of the input consists of a single integer, NN.

The next line contains NN space-separated integers, the permutation of the first NN integers.

Output Specification

Output, on a single line, the minimum number of swaps needed.

Sample Input

3
2 1 3

Sample Output

2

Comments

There are no comments at the moment.