| Fişierul intrare/ieşire: | proximity.in, proximity.out | Sursă | IIOT 2021-22 Runda 3 |
| Autor | Stefan Dascalescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | proximity.out |
|---|---|
| 5 5 2 4 3 1 | 1 |
| proximity.in | proximity.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.
