Shrek's Song of the Swamp

Limits: 4 sec., 512 MiB

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, \(s\), is composed of various sounds, each represented by an integer. The song contains \(n\) 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 \(s\) 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 \(n\) — 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.

Output

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

Constraints

\(1 \leq n \leq 10^6\),

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

Samples

Input (stdin) сopy	Output (stdout) сopy
9 1 2 3 1 3 1 2 3 2	5

Input (stdin) сopy	Output (stdout) сopy
6 3 4 10 1 -3 5	0

Input (stdin) сopy	Output (stdout) сopy
4 1 2 1 1	3

Notes

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.