#1957 · Dãy số đẹp

Cậu bé An rất yêu thích các con số. Một ngày nọ, An đang chơi với một dãy số nguyên dương. Cậu gọi một dãy số là “đẹp” nếu không có hai phần tử liên tiếp nào giống nhau.

Ví dụ:

• [1, 2, 1, 2] là đẹp
• [3, 3, 1, 2] không đẹp (vì có hai số 3 liên tiếp)

An muốn biết: nếu ta xóa đi một số phần tử trong dãy sao cho thứ tự còn lại vẫn được giữ nguyên, thì độ dài lớn nhất của một dãy đẹp thu được là bao nhiêu?

• Dòng đầu tiên là số nguyên N (1 ≤ N ≤ 10⁵) — số lượng phần tử của dãy.
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁹) — các phần tử của dãy ban đầu.

Một số nguyên duy nhất — độ dài dài nhất của một dãy con đẹp có thể tạo ra bằng cách xóa một số phần tử.