Þið vinirnir hafið ákveðið að fara saman í karaoke. Þið eruð
búin að velja $n$ lög sem
þið ætlið að syngja og þar sem þú ert yngstur í vinahópnum færð
þú fyrsta val á lögum til að syngja. Eftir að hafa lesið
listann ertu búinn að úthluta hverju lagi einkunn eftir því
hvað þér finnst vera mikil stemming í laginu. Þú ert búinn að
ákveða að lögin sem þú syngur þurfa að vera í annað hvort
vaxandi eða minnkandi einkunnarröð. Svo þú getur sungið lög með
stemmingareinkunnir $1, 3,
5$ og $3, 2, 1$, en
ekki $5, 7, 1$ og
$2, 2$. Einnig vilt þú
syngja sem flest lög. Hvað getur þú sungið mörg lög fylgjandi
þessum reglum?
Inntak
Fyrsta lína inntaksins inniheldur eina heiltölu $n$ ($1
\leq n \leq 10^5$). Næsta lína inntaksins inniheldur
$n$ heiltölur $x$ ($1
\leq x \leq 10^9$), þar sem $j$-ta slíka talan svarar til
einkunnarinnar á $j$-ta
laginu á listanum.
Úttak
Úttakið skal innihalda eina heiltölu, mesta fjölda laga sem
þú getur sungið.
| 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
|
