Mock CCC '18 Contest 5 J4/S2 - Carol's Cute Carols

View as PDF

Submit solution



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

Problem type

Carol enjoys caroling.

Having finished writing the CCC, Carol is now free from the constraints that CCC put on her blade and soul. She now moves to a different problem - giving out gifts for Valentine's Day.

She has a list of N gifts that she needs to give out to her N favorite people. Each gift has a distinct importance value v_i, where lower values of v_i denote more importance, in the vein of being able to say that the person receiving the gift with value v_i is her v_i'th favorite person.

While thinking about carols, Carol realizes that she wants to give the gifts out in increasing order of importance to her N favorite people. The gifts are currently strewn in a line, and some of them are quite fragile. Carol wants to sort the gifts in increasing order, but due to the fragility of some of the gifts, she will only swap two gifts if they are adjacent. Carol, being the Carol that she is, will sing a carol every time she swaps two gifts.

Carol's voice will get hoarse though if she carols too much. Consequently, she wishes to minimize the number of swaps she needs to perform to get all of the gifts sorted in proper order. Note that in the proper ordering, the first gift is the least important and the last gift is the most important, and as Carol gives out gifts, the importance of each gift given is larger than that of the preceding gift.

Constraints

1 \le N \le 10^3

v_i form a permutation of the first N positive integers.

Input Specification

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

The next line contains N space-separated integers, the values v_1 through v_N representing the importance values of the N gifts.

Output Specification

Output, on a single line, the minimum number of carols Carol needs to sing to sort all the gifts.

Sample Input

3
2 1 3

Sample Output

2

Comments

There are no comments at the moment.