Hide

Problem I
Karaoke

Languages en is

You and your friends have decided to go to karaoke. You have chosen $n$ songs to sing and since you are the youngest you get first choice of which of the songs you get to sing. After carefully reading the list you have assigned each song a score based on how exciting the song is. You are determined to sing as many songs as you can, but you want all the songs you sing to be in either increasing or decreasing order of excitement. So you could sing songs with scores $1, 3, 5$ and $3, 2, 1$, but not $5, 7, 1$ and $2, 2$. What is the maximum number of songs you could sing following these rules.

Input

The first line of the input contains a single integer $n$ ($1 \leq n \leq 10^5$). The second line of the input contains $n$ integers $x$ ($1 \leq x \leq 10^9$), where the $j$-th such number corresponds to the excitement score of the $j$-th song on the list.

Output

The output should include a single integer, the maximum number of songs you can sing.

Sample Input 1 Sample Output 1
6
3 4 2 5 1 6
4
Sample Input 2 Sample Output 2
5
1 2 1 2 1
2
Sample Input 3 Sample Output 3
10
1 2 1 3 4 5 6 7 1 8
8
Sample Input 4 Sample Output 4
7
7 5 6 4 3 1 2
5

Please log in to submit a solution to this problem

Log in