| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 19 | 9 | 8 | 44.444% |
The $N$ residents of Line Town have arranged themselves in a line. Initially, the residents have happiness values of $h_{1}, h_{2}, \ldots, h_{N}$ from left to right along the line.
Since you are the mayor of Line Town, you are implementing the third pillar of your plan entitled "Community, Candy, and Organization" (CCO). As such, you have taken the mayoral power to swap the residents' locations. In one swap, you may tell two adjacent residents to swap their positions in the line. However, this swap will cause both residents to negate their happiness values.
You would like to perform some swaps so that the residents' happiness values are in nondecreasing order from left to right in the line. Determine whether this is possible, and if so, the minimum number of swaps needed.
The first line of input contains a single integer $N$.
The next line of input contains $N$ integers $h_{1}, \ldots, h_{N}$ $(-10^{9} \le h_{i} \le 10^{9}),ドル the happiness values of the residents from left to right.
On a single line, output the minimum number of swaps, or -1 if the task is impossible.
6 -2 7 -1 -8 2 8
3
It is possible to perform 3ドル$ swaps as follows:
The residents are now arranged in non-decreasing order of happiness values as required. No non-decreasing arrangement can be obtained with less than 3ドル$ swaps.
4 1 -1 1 -1
-1
There is no sequence of swaps that will place residents in non-decreasing order of happiness values.