Умова задачі

Японський архіпелаг — це довгий і вузький архіпелаг. Паралельними розмежувальними лініями Японський архіпелаг поділено на $N$ ділянок. Ділянки пронумеровано по порядку від одного краю до іншого числами від $1$ до $N$. Висота ділянки $i$ ($1 \le i \le N$) дорівнює $A_i$.

Японський архіпелаг оточений морем, а рівень моря є сталим незалежно від місця. Ділянка, висота якої строго більша за рівень моря, називається суходолом.

Неперервна частина суходолу називається островом. Точніше кажучи: для цілих чисел $l$, $r$ ($1 \le l \le r \le N$) частину Японського архіпелагу, що складається з ділянки $l$, ділянки $l+1$, $\dots$, ділянки $r$, називають областю $[l, r]$. Область $[l, r]$, яка задовольняє такі умови, називається островом:

• Ділянка $l$, ділянка $l+1$, $\dots$, ділянка $r$ — усі є суходолом.
• Якщо $l > 1$, то ділянка $l-1$ не є суходолом.
• Якщо $r < N$, то ділянка $r+1$ не є суходолом.

Через підвищення рівня моря Японський архіпелаг поступово занурюється під воду. Зараз рівень моря дорівнює $0$, але з часом він поступово піднімається, аж поки вся Японія не перетвориться на море.

JOI помітив, що зі зростанням рівня моря кількість островів у Японії збільшується та зменшується. Знайдіть максимальну кількість островів за період від теперішнього моменту доти, доки в Японії зовсім не залишиться суходолу (включно з теперішнім моментом).

Обмеження

• $1 \le N \le 100000 (= 10^5)$
• $0 \le A_i \le 1000000000 (= 10^9)$ ($1 \le i \le N$)

Введення та виведення

Вхідні дані
Вхідні дані подаються зі стандартного потоку введення в такому форматі:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Вихідні дані
Виведіть в $1$ рядку максимальну кількість островів за період від теперішнього моменту доти, доки в Японії не залишиться суходолу (включно з теперішнім моментом).

Підзадачі

1. ($7$ балів) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ балів) $N \le 2000$
3. ($85$ балів) Додаткових обмежень немає.

Приклади вводу та виводу

Приклад вводу 1

6
0 1 2 1 3 2

Приклад виводу 1

2

• Коли рівень моря не менший за $0$ і менший за $1$, ділянки $2, 3, 4, 5, 6$ є суходолом. Оскільки область $[2, 6]$ є єдиним островом, кількість островів дорівнює $1$.
• Коли рівень моря не менший за $1$ і менший за $2$, ділянки $3, 5, 6$ є суходолом. Оскільки область $[3, 3]$ та область $[5, 6]$ є островами, кількість островів дорівнює $2$.
• Коли рівень моря не менший за $2$ і менший за $3$, лише ділянка $5$ є суходолом. Оскільки область $[5, 5]$ є єдиним островом, кількість островів дорівнює $1$.
• Коли рівень моря досягає $3$, суходолу не залишається, і кількість островів стає рівною $0$.

Отже, максимальна кількість островів дорівнює $2$, тому виводиться $2$.

Приклад вводу 2

6
3 2 3 0 2 0

Приклад виводу 2

2

• Коли рівень моря не менший за $0$ і менший за $2$, ділянки $1, 2, 3, 5$ є суходолом. Оскільки область $[1, 3]$ та область $[5, 5]$ є островами, кількість островів дорівнює $2$.
• Коли рівень моря не менший за $2$ і менший за $3$, ділянки $1, 3$ є суходолом. Оскільки область $[1, 1]$ та область $[3, 3]$ є островами, кількість островів дорівнює $2$.
• Коли рівень моря досягає $3$, суходолу не залишається, і кількість островів стає рівною $0$.

Отже, максимальна кількість островів дорівнює $2$, тому виводиться $2$.

Приклад вводу 3

10
4 1 2 1 2 3 5 4 3 2

Приклад виводу 3

3