Given a sequence $h_1, \dots, h_n$ of length $n$, you can perform the following operation any number of times:
- Choose an index $i$ such that $1 \le i \le n-1$.
- Set $h'_i = -h_{i+1}$ and $h'_{i+1} = -h_i$, leaving all other elements unchanged.
You need to make the sequence $h$ monotonically non-decreasing. Determine if a valid sequence of operations exists, and if so, minimize the number of operations.
Input
The first line contains a positive integer $n$, representing the length of the sequence.
The second line contains $n$ integers $h_1, \dots, h_n$.
Output
If no valid sequence of operations exists, output -1. Otherwise, output a single non-negative integer representing the minimum number of operations.
Examples
Input 1
6 -2 7 -1 -8 2 8
Output 1
3
Note 1
The chosen indices $i$ are $2, 4, 3$ in order.
Input 2
4 1 -1 1 -1
Output 2
-1
Constraints
For all test cases, it is guaranteed that $1 \le n \le 5 \times 10^5$ and $-10^9 \le h_i \le 10^9$.
| Subtask ID | $n \le$ | Special Property | Score |
|---|---|---|---|
| $1$ | $2000$ | $\lvert h_i\rvert=1$ | $10$ |
| $2$ | $5\times 10^5$ | $\lvert h_i\rvert=1$ | $10$ |
| $3$ | $2000$ | $\lvert h_i\rvert\le 1$ | $10$ |
| $4$ | $5\times 10^5$ | $\lvert h_i\rvert\le 1$ | $14$ |
| $5$ | $2000$ | $\lvert h_i\rvert$ are all distinct | $20$ |
| $6$ | $5\times 10^5$ | $\lvert h_i\rvert$ are all distinct | $16$ |
| $7$ | $2000$ | $8$ | |
| $8$ | $5\times 10^5$ | $12$ |