The cows are in a particularly mischievous mood today! All Farmer John wants to do is take a photograph of the cows standing in a line, but they keep moving right before he has a chance to snap the picture.

Specifically, each of FJ'sN cows(1 \le N \le 10^5) has an integer height from1 to N. FJ wants to take a picture of the cows standing in line in a very specific ordering. If the cows have heights h_1, \dots, h_K when lined up from left to right, he wants the cow heights to have the following three properties:

He wants the cow heights to increase and then decrease. Formally, there must exist an integeri such that h_1 \le \dots \le h_i \ge \dots \ge h_K.

He does not want any cow standing next to another cow with exactly the same height. Formally, h_i \neq h_{i+1} for all 1 \le i < K.

He wants the picture to be symmetric. Formally, if i + j = K+1, then h_i = h_j.

FJ wants the picture to contain as many cows as possible. Specifically, FJ can remove some cows and rearrange the remaining ones. Compute the maximum number of cows FJ can have in the picture satisfying his constraints.

#8413 upload 12 done 2 how_to_reg 2

More Cow Photos timer 1s memory 1024MB

#8413

More Cow Photos 1s 1024MB