Cho dãy số gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~. Cần chia dãy thành các nhóm thoả mãn:

• Mỗi nhóm chứa ít nhất một phần tử;

• Mỗi nhóm là các phần tử liên tiếp;

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

• Không có giá trị nào xuất hiện trong nhiều hơn ~2~ nhóm.

Ví dụ: ~A = [1, 2, 1, 1, 1, 2]~, có thể chia thành ~4~ nhóm ~[1] \mathbin{|} [2] \mathbin{|} [1, 1, 1] \mathbin{|} [2]~. Cách chia không đúng là ~[1] \mathbin{|} [2] \mathbin{|} [1, 1] \mathbin{|} [1, 2]~ vì số ~1~ xuất hiện trong ~3~ nhóm.

Yêu cầu: Hãy tìm cách chia dãy số ra được nhiều nhóm nhất. In ra số lượng nhóm nhiều nhất có thể chia thoả mãn yêu cầu.

Input

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

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(\lvert A_i \rvert \le 10^9)~.

Output

• Một số nguyên dương là số lượng nhóm nhiều nhất chia được.

Scoring

Sample Input 1

5
1 2 1 2 1

Sample Output 1

3

Notes

Có thể chia dãy thành ba nhóm hợp lệ là ~[1] \mathbin{|} [2] \mathbin{|} [1, 2, 1]~. Giá trị ~1~ và ~2~ đều chỉ xuất hiện trong hai nhóm. Không thể chia dãy thành bốn nhóm hợp lệ.

Cách chia khác cũng thoả mãn: ~[1, 2, 1] \mathbin{|} [2] \mathbin{|} [1]~.