Fişierul intrare/ieşire:proximity.in, proximity.outSursăIIOT 2021-22 Runda 3
AutorStefan DascalescuAdăugată destefdascalescuStefan Dascalescu stefdascalescu
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sorting Proximity

As a New Year's resolution, our heroes want everything around them to be clean and perfectly arranged. Thus, they now want to apply their new ideals on their daily work, namely handling the various data structures they are using.

This time around, they got an array of length n and they define the sorting proximity of the array as the number of swaps which have to be done in order to sort the array, if we use the bubble sort algorithm.

Namely, as long as the array is not sorted yet, the bubble sort algorithm iterates through the array and every time two adjacent values are wrongly placed relative to one another, they are swapped. The sorting proximity is the number of times this happens during the algorithm.

For example, if we have the array 4, 2, 3, 5, 1, the sorting proximity of the array is 6.

Now, our heroes want to improve the sorting proximity of the array and they asked for your help. Your job is to swap two integers from the array (they don't have to be adjacent) so that the sorting proximity of the resulting array is minimal. Even though the swap may not improve the answer, you must do it.

Date de intrare

The first line of the input file proximity.in contains n, the number of integers from the array.

The second line of the input contains the array v.

Date de ieşire

The output file proximity.out contains the minimal sorting proximity we can get if we swap exactly two values from the array.

Restricţii

  • 1 ≤ n ≤ 10^5
  • 1 ≤ v[i] ≤ 10^9
  • For tests worth 20 points, 1 ≤ n ≤ 10^3
  • For tests worth 40 more points, all the values from the array are distinct.

Exemplu

proximity.inproximity.out
5
5 2 4 3 1
1
proximity.inproximity.out
5
3 1 7 9 5
2

Explicaţie

For the first sample test case, we can swap 5 and 1 and we will get the array 1, 2, 4, 3, 5 which has the sorting proximity equal to 1.

For the second sample test case, we can swap 5 and 7 and we will get the array 3, 1, 5, 9, 7 which has the sorting proximity equal to 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?