The 2015 International Olympiad in Informatics will be held in Kazakhstan. The word "Kazakh" is sometimes spelled "QAZAQ" in the alphabet. This "QAZAQ" is a palindrome. Upon learning this, JOI-kun became fond of palindromes and decided to create palindromes from strings he encounters.

JOI-kun has found a string of length $N$. Each character is assigned an integer from $1$ to $C$, and we represent the sequence of integers corresponding to the string as $S = (S_1, S_2, \dots, S_N)$. A sequence $(S_i, S_{i+1}, \dots, S_j)$ extracted from the $i$-th to the $j$-th element of this sequence ($1 \le i \le j \le N$) is called a segment $(i, j)$. A segment $(i, j)$ is a palindrome if it is equal to its reverse, that is, if $(S_i, S_{i+1}, \dots, S_j) = (S_j, S_{j-1}, \dots, S_i)$ holds.

JOI-kun creates a palindrome through the following operation:

1. First, choose one segment of $S$. Let the chosen segment be $T$.
2. Let $T'$ be the segment $T$ sorted in ascending order.
3. Replace the segment $T$ in the sequence $S$ with $T'$. Let the resulting sequence be $S'$. That is, when JOI-kun chooses a segment $(i, j)$, let $T'_i \le T'_{i+1} \le \dots \le T'_j$ be the elements of $S_i, S_{i+1}, \dots, S_j$ sorted in ascending order, and let $S' = (S_1, S_2, \dots, S_{i-1}, T'_i, T'_{i+1}, \dots, T'_j, S_{j+1}, \dots, S_N)$.
4. Then, search for a segment in $S'$ that is a palindrome.

JOI-kun wants to create the longest possible palindrome using this operation.

Task

Given the sequence $S$ representing the string found by JOI-kun, find the maximum length of a palindrome that JOI-kun can create.

Input

Read the following from standard input:

• The first line contains two space-separated integers $N$ and $C$. $N$ represents the length of the string found by JOI-kun, and $C$ represents the upper bound of the integers assigned to the characters.
• The following $N$ lines contain information about the sequence $S$ representing the string found by JOI-kun. The $i$-th line ($1 \le i \le N$) contains the integer $S_i$, which represents the $i$-th integer of the sequence $S$.

Output

Output the maximum length of a palindrome that JOI-kun can create as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 3\,000$.
• $1 \le C \le 3\,000$.
• $1 \le S_i \le C$ ($1 \le i \le N$).

Subtasks

Subtask 1 [10 points]

The following conditions are satisfied:

• $N \le 50$.
• $C \le 50$.

Subtask 2 [90 points]

There are no additional constraints.

Examples

Input 1

12 26
26
17
17
17
1
26
1
17
19
20
1
14

Output 1

8

Note 1

In this input example, $N = 12, C = 26$, and $S = (26, 17, 17, 17, 1, 26, 1, 17, 19, 20, 1, 14)$. Here, by sorting the segment $(4, 8)$ in ascending order, we get $S' = (26, 17, 17, 1, 1, 17, 17, 26, 19, 20, 1, 14)$, and the segment $(1, 8)$ becomes a palindrome. The length of this palindrome is 8, which is the longest.

Input 2

4 3
1
2
3
2

Output 2

3

Note 2

In this input example, $S = (1, 2, 3, 2)$. Here, by sorting the segment $(1, 1)$ in ascending order, we get $S' = (1, 2, 3, 2)$. $S$ and $S'$ are the same sequence. The segment $(2, 4)$ of $S'$ is a palindrome. The length of this palindrome is 3, which is the longest.