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
|