הפרות של Farmer John רוצות לקפוץ מעל הירח כמו בשיר הילדים האהוב עליהן. לרוע המזל פרות אינן יכולות לקפוץ.

רופא האליל המקומי ערבב $P$ שיקויים ($1 \le P \le 150{,}000$) שיעזרו. יש לקחתם בדיוק בסדר יצירתם, אך אפשר לדלג על חלקם.

לכל שיקוי «עוצמה» ($1 \le strength \le 500$) המשפרת קפיצה. לקיחתו בצעד אי־זוגי מגדילה את הקפיצה, ובצעד זוגי מקטינה אותה. לפני השיקויים היכולת היא כמובן0.

אין לקחת שיקוי פעמיים. לאחר ההתחלה יש לקחת אחד בכל צעד מזמן1. בכל תור אפשר לדלג על שיקוי אחד או יותר.

קבעו אילו שיקויים לקחת לקפיצה הגבוהה ביותר.

קלט

• שורה $1$: שלם $P$.
• שורות $2..P+1$: כל שורה מכילה שלם, עוצמת שיקוי. שורה2 נותנת את הראשון, שורה3 את השני, וכן הלאה.

פלט

• שורה $1$: שלם אחד, הקפיצה המרבית האפשרית.

דוגמאות

קלט 1

8
7
2
1
8
4
3
5
6

פלט 1

17