Longest Beautiful Subsequence

You are given a sequence of n integers. A beautiful subsequence is defined as a subsequence that satisfies the following condition: for any two consecutive elements (in the original sequence order) that are selected, they must not be equal. In other words, when picking elements from the sequence to form the subsequence, no two adjacent elements in the original sequence (if both are chosen) should be the same.

Your task is to determine the length of the longest beautiful subsequence from the given sequence.

Note: The subsequence is not required to be contiguous, but the relative order of elements must be preserved.

Example: For the sequence [1, 2, 2, 3, 1], one possible beautiful subsequence is [1, 2, 3, 1] which has a length of 4.

inputFormat

The input consists of two lines:

1. The first line contains an integer n (0 ≤ n ≤ 10⁵), representing the length of the sequence.
2. The second line contains n space separated integers representing the sequence.

outputFormat

Output a single integer on one line, representing the length of the longest beautiful subsequence.

5
1 2 2 3 1

4