تريد التدرب على التزلج في مسار معطى. يتكوّن المسار من نقطة بداية و$N$ نقطة وسطية ونقطة نهاية. يبدأ التدريب عند نقطة البداية بسرعة $0$، ويمر بالنقاط الوسطية من $1$ إلى $N$ بترتيب أرقامها تصاعديًا، وينتهي بعد الوصول إلى نقطة النهاية بسرعة $0$.

لكل نقطة وسطية حد للسرعة $V_i$، لذا يجب تعديل سرعتك أثناء الانتقال بحيث لا تتجاوز حد السرعة للنقطة التالية التي تزورها. يمكنك زيادة السرعة بالمقدار الذي تريده، لكن عند إبطائها لا يمكنك تخفيضها إلا بمقدار $1$ عن سرعتك عند آخر نقطة زرتها. لا يمكن أن تكون السرعة $0$ في أي موضع سوى نقطتي البداية والنهاية. ويمكنك أيضًا إبقاء السرعة دون تغيير.

نتيجة التدريب تساوي مجموع السرعات عند جميع النقاط، وتريد تعظيمها. عند إعطائك حدود السرعة للمسار، أوجد أكبر نتيجة تدريب يمكنك تحقيقها عليه.

مثلًا، افترض وجود ثلاث نقاط وسطية بحدود سرعة $V=[2,3,1]$. إذا حافظت على سرعة $3$ عند النقطة الوسطية $2$، فلن تتمكن من تعديلها لتصبح على الأكثر $1$ عند النقطة الوسطية $3$. إحدى طرق التدريب الممكنة هي السرعات $[2,2,1]$، ومجموعها $2+2+1=5$. ومن الطرق الممكنة الأخرى $[1,1,1]$ و$[1,2,1]$، لكن مجموع سرعاتها لا يتجاوز $5$. لذا فإن أكبر نتيجة تدريب على هذا المسار هي $5$.

القيود

• جميع الأعداد المعطاة أعداد صحيحة.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

المهام الفرعية

1. 8 نقطة: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 نقطة: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 نقطة: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 نقطة: $N \le 5000$
5. 53 نقطة: لا توجد قيود إضافية.

الإدخال

يحتوي السطر الأول على $N$.

يحتوي السطر الثاني على $V_1,V_2,\ldots,V_N$ بهذا الترتيب، مفصولة بمسافات.

الإخراج

اطبع الإجابة في السطر الأول.

أمثلة

الإدخال 1

3
2 3 1

الإخراج 1

5

الإدخال 2

4
23 7 1 5

الإخراج 2

7