وصف المسألة

الأرخبيل الياباني هو أرخبيل طويل وضيق. ينقسم الأرخبيل الياباني بواسطة خطوط حدودية متوازية إلى $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