E. Sixty Nine
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an array of integers $$$a = a_1a_2...a_n$$$, now you like to see number $$$69$$$ as many as possible in the array, for this goal there are two operations that can be used in a move :

  • choose a prefix of the array and subtract $$$1$$$ from all of the elements of the chosen prefix.
  • choose a suffix of the array and subtract $$$1$$$ from all of the elements of the chosen suffix.

Note that you can choose exactly one of the operations above at each moment and you can do each operation many times (possibly $$$0$$$), also numbers can become negative during the operations.

Now your task is to find the maximum number of $$$69$$$ you can obtain in the array.

Input

In the first line of input you'll be given a number $$$n$$$ which shows the length of the array.

$$$$$$1 \le n \le 2000$$$$$$

In the second line you'll receive the array.

$$$$$$1 \le a_i \le 10^9$$$$$$

Output

Print the maximum number of $$$69$$$ you can obtain with the given operations in the array.

Examples
Input
7
64 69 72 72 72 69 64
Output
4
Input
7
72 77 71 5 73 71 72
Output
5
Note

Operations of testcase $$$2$$$ :

  • choose the prefix of length $$$5$$$
  • choose the prefix of length $$$5$$$
  • choose the prefix of length $$$2$$$
  • choose the suffix of length $$$3$$$
  • choose the suffix of length $$$3$$$
  • choose the suffix of length $$$1$$$

The array after the operations : $$$a = $$${$$$69, 74, 69, 3, 69, 69, 69$$$}.