Page not loading? Try clicking here.
Placeholder

#1814

Insertion Sort Movements 1s 32MB

Problems

We want to perform an insertion sort on a sequence A consisting of distinct numbers.

For example, if the array A contains 20, 40, 30, 10, the insertion sort proceeds as follows:

  • i = 1 → 20, 40, 30, 10 | movements: 0

  • i = 2 → 20, 40, 30, 10 | movements: 0

  • i = 3 → 20, 30, 40, 10 | movements: 1 (40 moves to make space for 30)

  • i = 4 → 10, 20, 30, 40 | movements: 3 (20, 30, 40 move to make space for 10)

The total number of movements for the insertion sort to complete is 4.


Input

The first line contains an integer N (1 ≤ N ≤ 50), the length of the sequence.

The second line contains N integers between -1000 and 1000. All numbers are distinct.


Output

Print a single integer representing the total number of element movements that occur during the insertion sort.


Example #1

4

20 40 30 10
4

Example #2

3

-1 1 0
1


Source

JUNGOL

You must sign in to write code.