At the end of the year, Eric has a chance to show off his garden that he has grown. His garden consists of an array of plants, each with a height of h_i. In order to impress other people, Eric wants to choose the longest possible subsequence that is beautiful.

Recall that a subsequence of array A is a list of elements, that can be obtained by deleting some elements of A, whilst maintaining the relative ordering.

A subsequence a₁, a₂, ..., a_n is beautiful if:

• n is odd.
• The sequence forms a palindrome such that the middle element is the maximum element.
• The difference between heights of consecutive plants is 1
• Except for the middle element, the left and right neighbours (if they exist) are not the same.

For example, the following subsequences are beautiful:

1 2 3 2 1
3 4 3
1

The following subsequences are not beautiful:

2 2
2 4 2
3 5 6 1

Help Eric find the length of the longest beautiful subsequence of his garden.

Input Format:

The first line an integer n, representing the number of plants in Eric's garden. The next line contains n integers, representing the heights of each plant

Output:

The length of the longest beautiful subsequence in Eric's garden

Sample Input:

5
3 6 7 4 3

Sample Output:

3

Sample Explanation:

In the first sample case, Eric can choose the sequence 3 4 3 of length 3