Bạn có ~n~ quả bóng được xếp trên ~1~ đường thẳng. Quả bóng thứ ~i~ có mã màu ~a_i~.

Bạn muốn tặng các quả bóng cho các em nhỏ học ở trường Tiểu học & Trung học cơ sở La Ngâu. Nhưng bạn không muốn các em có được chúng một cách dễ dàng nên bạn đặt ra một thử thách. Các em có thể thực hiện các hành động sau:

• Chọn ~i~ và ~j~ sao cho ~1 \le i \lt j \le n~ và ~a_i = a_j~.
• Xóa đoạn ~a_i, a_{i+1}, a_{i+2}, ..., a_j~ ra khỏi dãy (và giảm chỉ số của các quả bóng bên phải ~a_j~ đi ~j-i+1~).

Các em nhỏ có thể lặp đi lặp lại các hành động trên và các quả bóng thuộc về các em nếu nó bị xóa ra khỏi hàng. Nhiệm vụ của các em nhỏ bây giờ là tìm cách để xóa được nhiều quả bóng nhất.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên dương ~n~ ~(n \le 10^6)~.
• Dòng thứ hai chứ ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \le n)~ lần lượt là mã màu của từng quả bóng, các số các nhau ít nhất một khoảng trắng.

Dữ liệu ra

Một dòng duy nhất chứa số lượng quả bóng lớn nhất mà các em nhỏ có thể nhận được.

Ràng buộc

• Có ~50\%~ số điểm ứng với ~n \le 5000~.
• Có ~50\%~ số điểm ứng với ~n \le 10^6~.

Ví dụ

Dữ liệu vào

4
1 4 1 2

Dữ liệu ra

3

Giải thích

Ở ví dụ ta chọn xóa đoạn ~[1, 3]~, khi đó các em nhận được ~3~ quả bóng.