The members of the Scientific Committee of the Junior Balkan Olympiad in Informatics 2012 really enjoy discussing problems at the dinner table (which is a long rectangular table where all committee members sit next to each other on one of the long sides of the table). The committee members are quirky people - they are happy with their placement at the table only when they sit between two people and both of their neighbors are either strictly taller than them or they are both strictly shorter than them. Curiously, no two committee members with equal height are seated next to each other.

Help Bidik, the person in charge of the dinner seating arrangement, and find the greatest number of Scientific Committee members that are seated consecutively and are all happy with their placement.


The first line of input contains one integer N (5 ≤ N ≤ 50000) - the number of committee members. The second line contains N positive integers Hi (100 ≤ Hi ≤ 1000000) - the heights of all committee members, as they are ordered at the table from left to right.

In test cases worth at least 30% of the full score, N will be smaller than 100 (5 ≤ N < 100).


Your program should output exactly one integer - the required maximum number of consecutive happy committee members.


Time limit: 1 second
Memory limit: 64 megabytes


170 172 169 173 150

160 165 170 175 180 185


Feedback: During the contest, your submissions for this task will be evaluated on 50% of the official test cases. After the evaluation of a submission is done, you will be shown a summary of the results.

 Submit your code