Sau khi chán các tác phẩm nghệ thuật hai chiều thông thường (và cũng bực bội vì người khác sao chép tác phẩm của mình), nữ họa sĩ bò vĩ đại Picowso đã quyết định chuyển sang phong cách một chiều tối giản hơn.

Mặc dù giờ đây các bức vẽ của cô có thể được mô tả bằng một mảng màu một chiều độ dài \(N\) (\(1 \leq N \leq 100\,000\)), phong cách vẽ của cô vẫn không thay đổi: cô bắt đầu với một bức vẽ trống rồi phủ lên đó lần lượt các "hình chữ nhật" bằng sơn; trong trường hợp một chiều này, chúng đơn giản là các đoạn. Cô sử dụng mỗi màu từ \(1 \ldots N\) đúng một lần, mặc dù cũng như trước đây, đến cuối cùng một số màu có thể bị che phủ hoàn toàn.

Picowso vô cùng thất vọng khi đối thủ Moonet dường như đã tìm ra cách sao chép ngay cả những bức vẽ một chiều này bằng một chiến lược tương tự như trong bài trước: Moonet sẽ tô một tập hợp các đoạn đôi một không giao nhau, đợi chúng khô, sau đó tô một tập hợp các đoạn đôi một không giao nhau khác, và cứ tiếp tục như vậy. Trong toàn bộ quá trình, Moonet chỉ có thể tô nhiều nhất một đoạn bằng mỗi màu. Hãy tính số lượt như vậy cần thiết để Moonet sao chép một bức vẽ một chiều cho trước của Picowso.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên trong khoảng \(0 \ldots N\), biểu thị màu của từng ô trong bức vẽ một chiều (\(0\) là một ô trống).

Dữ liệu ra

In số lượt ít nhất cần thiết để sao chép bức vẽ, hoặc \(-1\) nếu đây không thể là một tác phẩm đích thực của Picowso (tức là cô không thể vẽ nó bằng cách phủ lần lượt các đoạn, mỗi màu một đoạn).

Ví dụ

7
0
1
4
5
1
3
3

2

Nguồn

USACO 2017 US Open Contest, Gold — Modern Art 2. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=743