Problem Description

T-san challenges various things under the motto of "impermanence." He has been participating in a certain contest for a long time, and the contest has a rating system where the rating changes every time he participates. These changes are summarized in a graph.

Now, T-san is looking at the graph plotting his rating fluctuations. Suddenly, he wants to create a polyline graph, which he calls an "unconstant graph," by removing some points from the graph and connecting them, so that it always fluctuates up and down. Furthermore, he is interested in the graph with the most points included.

You have decided to help T-san by finding the maximum number of points in an "unconstant graph" that can be created from the graph plotting his rating fluctuations.

You are given T-san's ratings after participating in a contest, in chronological order, with $ N $ ratings. From these, remove some points to create an "unconstant graph," and find the maximum number of possible points. If an unconstant graph cannot be created, output $ 0 $.

A graph $X=\{x_1,x_2,x_3,..x_n\}$ is an "unconstant graph" if $ |X| $ is $ 3 $ or more and either $ x_1 < x_2 > x_3 < x_4 > ... $ or $ x_1 > x_2 < x_3 > x_4 < ... $ holds. In other words, if the number of included vertices is less than $ 3 $, it is not an "unconstant graph."

Input Format

The input is given from the standard input in the following format:

$ N $ $ R_1 $ $ R_2 $ … $ R_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 3000)$, representing the number of times T-san has participated in the contest.
• The second line contains the ratings $R_i\ (-10^5\ ≦\ R_i\ ≦\ 10^5)$ after T-san participated in the $i\ (1\ ≦\ i\ ≦\ N)$th contest, separated by spaces.

Output Format

Find the maximum number of points in an "unconstant graph" that can be created from the given graph by removing some points and output it in one line. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

4
1 2 5 1

Sample Output #1

3

Sample Input #2

5
1 2 3 4 5

Sample Output #2

0

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分