Theo từ điển PWN, "lider" (lãnh đạo) là "người đứng đầu một đảng chính trị, công đoàn hoặc các tổ chức xã hội khác". Tuy nhiên, trong thuật toán, "lider" của một dãy các phần tử là phần tử có số lần xuất hiện nhiều hơn một nửa độ dài của dãy đó. Ví dụ, lider của dãy $[7, 2, 5, 7, 7]$ là số $7$, trong khi dãy $[2, 3, 2, 3]$ không có lider.

Trong bài toán này, chúng ta tập trung vào ý nghĩa thứ hai của từ "lider". Cho một dãy số, nhiệm vụ của bạn là chia nó thành số lượng dãy con tối thiểu (không nhất thiết phải liên tiếp), trong đó mỗi dãy con đều có một lider, và in ra số lượng tối thiểu đó. Có thể chứng minh rằng việc phân chia như vậy luôn luôn khả thi.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 500\,000$), biểu thị độ dài của dãy.

Dòng thứ hai của dữ liệu vào chứa dãy gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Dữ liệu ra

Dòng duy nhất của dữ liệu ra chứa một số nguyên, biểu thị số lượng dãy con tối thiểu có thể chia dãy đầu vào thành, sao cho mỗi dãy con kết quả đều có một lider.

Ví dụ

Ví dụ 1

5
1 2 3 1 2

Kết quả 1

2

Ghi chú

Dãy đầu vào có thể được chia, ví dụ, thành các dãy $[1, 3, 1]$ và $[2, 2]$. Bằng cách này, cả hai dãy kết quả đều có lider (lần lượt là các số $1$ và $2$).