Picowso decided to switch to 1D style.
Now her paintings can be described by a 1-dimensional array of colors of length NN (1≤N≤100,000). But her style remained the same: He starts on an empty segment and draws in segments. It uses each of the 1…N colors exactly once, although some of the colors may be completely hidden by the end of the drawing.
Moonet, Picowso's rival, figured out how to copy Picowso's paintings. It draws many non-connecting intervals, and so on. Moonet can draw at most one interval of each color during the entire process. Calculate the number of such rounds required by Moonet to copy the 1D Picowso painting.
INPUT FORMAT:
The first line of input contains N, and the next N lines contain an integer in the range 0…N indicating the color of each cell on the 1-dimensional canvas (0 for an empty cell).
OUTPUT FORMAT:
Print the minimum number of rounds required to copy the given pattern, or -1 if it is not possible to repeat this pattern in a style authentic to Picowso's style (that is, it cannot be drawn in layers of spacing sequences, one for each color).
|
Enter |
Output |
|
7
0
1
4
5
1
3
3
|
2 |