Deskripsi Masalah

Kepulauan Jepang adalah kepulauan yang panjang dan sempit. Kepulauan Jepang dibagi menjadi $N$ petak oleh garis-garis batas yang sejajar. Petak-petak tersebut diberi nomor dari $1$ hingga $N$ secara berurutan dari salah satu ujungnya. Ketinggian petak $i$ ($1 \le i \le N$) adalah $A_i$.

Kepulauan Jepang dikelilingi oleh laut, dan tinggi permukaan laut selalu konstan di mana pun. Petak yang ketinggiannya lebih tinggi daripada tinggi permukaan laut disebut daratan.

Bagian daratan yang berurutan secara kontinu disebut pulau. Lebih tepatnya adalah sebagai berikut. Untuk bilangan bulat $l$, $r$ ($1 \le l \le r \le N$), bagian dari Kepulauan Jepang yang terdiri dari petak $l$, petak $l+1$, $\dots$, petak $r$ disebut wilayah $[l, r]$. Wilayah $[l, r]$ yang memenuhi syarat-syarat berikut disebut pulau:

• Petak $l$, petak $l+1$, $\dots$, petak $r$ semuanya adalah daratan.
• Jika $l > 1$, maka petak $l-1$ bukan daratan.
• Jika $r < N$, maka petak $r+1$ bukan daratan.

Akibat naiknya permukaan laut, Kepulauan Jepang tenggelam sedikit demi sedikit. Tinggi permukaan laut saat ini adalah $0$, tetapi seiring berjalannya waktu tingginya perlahan-lahan naik, hingga akhirnya seluruh Jepang menjadi laut.

JOI menyadari bahwa ketika tinggi permukaan laut naik, jumlah pulau di Jepang bertambah dan berkurang. Carilah nilai maksimum dari jumlah pulau selama periode sejak saat ini hingga tidak ada lagi daratan yang tersisa di Jepang (termasuk saat ini).

Batasan

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

Masukan / Keluaran

Masukan
Masukan diberikan dari Masukan Standar dalam format berikut:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Keluaran
Keluarkan dalam $1$ baris nilai maksimum dari jumlah pulau selama periode sejak saat ini hingga tidak ada lagi daratan di Jepang (termasuk saat ini).

Subsoal

1. ($7$ poin) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ poin) $N \le 2000$
3. ($85$ poin) Tidak ada batasan tambahan.

Contoh Masukan / Keluaran

Contoh Masukan 1

6
0 1 2 1 3 2

Contoh Keluaran 1

2

• Ketika tinggi permukaan laut minimal $0$ dan kurang dari $1$, petak $2, 3, 4, 5, 6$ adalah daratan. Karena wilayah $[2, 6]$ adalah satu-satunya pulau, maka jumlah pulau adalah $1$.
• Ketika tinggi permukaan laut minimal $1$ dan kurang dari $2$, petak $3, 5, 6$ adalah daratan. Karena wilayah $[3, 3]$ dan wilayah $[5, 6]$ adalah pulau, maka jumlah pulau adalah $2$.
• Ketika tinggi permukaan laut minimal $2$ dan kurang dari $3$, hanya petak $5$ yang merupakan daratan. Karena wilayah $[5, 5]$ adalah satu-satunya pulau, maka jumlah pulau adalah $1$.
• Ketika tinggi permukaan laut mencapai $3$, tidak ada lagi daratan, dan jumlah pulau menjadi $0$.

Oleh karena itu, nilai maksimum dari jumlah pulau adalah $2$, sehingga keluarkan $2$.

Contoh Masukan 2

6
3 2 3 0 2 0

Contoh Keluaran 2

2

• Ketika tinggi permukaan laut minimal $0$ dan kurang dari $2$, petak $1, 2, 3, 5$ adalah daratan. Karena wilayah $[1, 3]$ dan wilayah $[5, 5]$ adalah pulau, maka jumlah pulau adalah $2$.
• Ketika tinggi permukaan laut minimal $2$ dan kurang dari $3$, petak $1, 3$ adalah daratan. Karena wilayah $[1, 1]$ dan wilayah $[3, 3]$ adalah pulau, maka jumlah pulau adalah $2$.
• Ketika tinggi permukaan laut mencapai $3$, tidak ada lagi daratan, dan jumlah pulau menjadi $0$.

Oleh karena itu, nilai maksimum dari jumlah pulau adalah $2$, sehingga keluarkan $2$.

Contoh Masukan 3

10
4 1 2 1 2 3 5 4 3 2

Contoh Keluaran 3

3