Shrek's Song of the Swamp#12976

Shrek's Song of the Swamp

4 seconds
512 megabytes
Hard

In the faraway land of Duloc, Shrek has discovered a magical melody hidden within the ancient Swamp Songs. The melody, however, is written as a sequence of numbers that represent the croaks of frogs and the rustling of leaves. To unlock its secrets, Shrek needs to decode the longest repeating pattern in this mystical sequence, following a specific set of rules.

Shrek’s melody sequence, , is composed of various sounds, each represented by an integer. The song contains sounds in total.

Shrek needs to find the longest possible subsequence that follows the strict Dulocian Harmony. To make the Dulocian Harmony, the following condition should hold: each sound must have a neighbour in the chosen subsequence that is the same sound as itself.

More precisely, Shrek must determine the length of the longest subsequence (not necessarily consecutive positions) x_1 x_2 \dots x_k of such that for all 1 \le i \le k either x_i=x_{i-1} or x_i=x_{i+1}, or both.

For example, Shrek can choose subsequences [1, 1, 1, 2, 2], [4, 4, 4, 4, 4] and can’t choose [1, 2, 2, 1, 1] since the first sound doesn’t have the same adjacent sounds.

Help Shrek unlock this enchanted melody!

Input

The first line contains a single integer — the number of sounds in Shrek’s song.

The second line contains integer values s_1, s_2, \dots, s_n representing the sounds from Shrek’s song.

1 \leq n \leq 10^6,

-10^{9} \leq s_i \leq 10^{9}.

Output

In the first line, print a single integer — the length of the longest subsequence in with the properties mentioned in the statement. If there are no such subsequences, print 0.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first sample, the longest subsequence with the properties described in the statement is s_1 s_4 s_6 s_7 s_9 = [1, 1, 1, 2, 2].

In the second sample, there is no subsequence with those properties.