Cho dãy số ~A~ độ dài ~N~, cần chia dãy ~A~ thành các nhóm thỏa mãn điều kiện:

• Mỗi phần tử thuộc đúng một nhóm.

• Mỗi nhóm chứa một số phần tử liên tiếp nhau.

• Trong mỗi nhóm có ít nhất ~2~ số có giá trị bằng nhau.

Tính số lượng nhóm tối đa có thể chia được.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~.

Dòng thứ hai chứa ~N~ số nguyên biểu diễn dãy ~A~ ~(|A_i| \le 10^9)~.

Output

Nếu tồn tại cách chia thì ghi trên một dòng số nhóm tối đa có thể chia, ngược lại ghi ~-1~.

Sample Input 1

6
1 1 3 1 2 1

Sample Output 1

2