Symmetric Cow Lineup

Farmer John's cows are acting mischievously today. He intended to take a photo of his cows lined up in a particular order, but they keep moving before he can snap the picture. He wants the photo to satisfy the following properties for the sequence of heights \(h_1, h_2, \dots, h_K\):

1. The heights first do not decrease and then do not increase. Formally, there exists an index \(i\) such that \[ h_1 \le h_2 \le \dots \le h_i \ge h_{i+1} \ge \dots \ge h_K, \] where the sequence is allowed to be non-decreasing up to the apex and non-increasing thereafter.
2. No two adjacent cows have the same height. In other words, for all \(1 \le j < K\), \[ h_j \neq h_{j+1}. \]
3. The photo is symmetric; that is, for every valid index \(i\) with \(1 \le i \le K\), \[ h_i = h_{K+1-i}. \]

Farmer John is allowed to remove some cows and reorder the remaining cows arbitrarily. Given the list of cow heights, determine the maximum number of cows that can be arranged in a line satisfying all the above conditions.

Note: Since the photo must be symmetric and unimodal with no adjacent equal heights, the final sequence will have an odd length. Specifically, if we denote the final sequence as \([a_1, a_2, \dots, a_m, a_{m-1}, \dots, a_1]\), then the left part \(a_1, a_2, \dots, a_m\) is strictly increasing and the right part is its mirror.

inputFormat

The first line contains a single integer \(N\) \( (1 \le N \le 10^5)\), which is the number of cows. The second line contains \(N\) integers, where each integer represents the height of a cow. Each height is an integer in the range \([1, N]\).

outputFormat

Output a single integer representing the maximum number of cows that can be included in the photo such that the resulting sequence satisfies all the given conditions.

sample

3
1 2 3

1