Maximum Removable Score in a Sequence

Given a sequence of integers, you are allowed to remove contiguous segments several times. Each removal yields a score equal to the length of the removed segment. After each removal the remaining parts of the sequence are concatenated (i.e. the left and right parts become adjacent).

A contiguous segment can be removed if it satisfies the following two conditions:

1. The absolute difference between every two consecutive elements is \(1\), i.e. \(|a_{i+1}-a_i|=1\).
2. If an element is not at the leftmost or rightmost end of the segment, then it cannot be smaller than both its adjacent elements (in other words, it cannot form a valley). Formally, for any index \(i\) with \(l<i<r\), it is not true that \(a_i<a_{i-1}\) and \(a_i<a_{i+1}\) simultaneously.

Some valid segments are: \([1,2,3,4,3]\), \([1,2]\), \([3,2]\) and \([3]\).

Note that when a segment is removed, the two parts left behind become adjacent and this may allow new valid removals. Your task is to compute the maximum total score (i.e. the maximum number of elements that can be removed) from the given sequence.

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 20)\), the length of the sequence.

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\), separated by spaces.

outputFormat

Output a single integer: the maximum total score (the maximum number of elements that can be removed by a series of valid removal operations).

sample

5
1 2 3 4 3

5