Есептің шарты

Жапон архипелагы — жіңішке әрі ұзын архипелаг. Жапон архипелагы параллель шекара сызықтарымен $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