No.1053 Gaming Stick
QCFium
tko919Problem Statement
You found a colorful stick lying on the roadside. This stick, lying horizontally in the left-right direction, is sufficiently thin and is divided into $N$ parts, and the $i$-th part from the left is painted in color $A_i$.
It is colorful as it is, but to make it more beautiful, you want it to satisfy the following: "each color, if it appears, appears entirely within one contiguous segment".
To this end, you perform the following operation $0$ or more times.
- Cut the stick at one place. Swap the positions of the 2 resulting sticks and join them. (Neither stick is reversed.)
A constraint violation was discovered in the test data, so it was corrected and a rejudge was performed. We apologize. (2020/05/15 21:47)
Input
$N$ $A_1\ A_2\ A_3\ \dots\ A_N$
$1 \le N \le 10^5$
$1 \le A_i \le N$
All inputs are integers.
Output
If it is impossible to satisfy the condition, print -1.
Otherwise, print the number of operations required to satisfy the condition.
Sample
Sample 1
Input
3 1 2 1
Output
1
For example, by cutting at the right end of the leftmost section and performing the operation, the colors of the stick after the operation become $2,1,1$ from left to right, which satisfies the condition.
Sample 2
Input
3 1 2 3
Output
0
The condition is already satisfied as it is.
Sample 3
Input
5 1 2 1 2 1
Output
-1
No matter what you do, the condition cannot be satisfied.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。