คำอธิบายโจทย์

หมู่เกาะญี่ปุ่นเป็นหมู่เกาะที่มีลักษณะแคบและยาว หมู่เกาะญี่ปุ่นถูกแบ่งออกเป็น $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$ บรรทัด

งานย่อย (Subtasks)

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