Farmer Johns Kühe wollen wie in ihrem Lieblingskinderreim über den Mond springen. Leider können Kühe nicht springen.

Der örtliche Medizinmann hat $P$ Tränke ($1 \le P \le 150{,}000$) dafür gemischt. Sie müssen genau in Herstellungsreihenfolge genommen werden, einige dürfen ausgelassen werden.

Jeder Trank hat eine „Stärke“ ($1 \le strength \le 500$), die das Springen verbessert. Einnahme in einem ungeraden Zeitschritt erhöht den Sprung, in einem geraden vermindert sie ihn. Vor der Einnahme ist die Sprungfähigkeit natürlich 0.

Kein Trank darf zweimal genommen werden. Sobald man beginnt, muss ab Zeitpunkt 1 in jedem Schritt ein Trank genommen werden. Pro Runde dürfen ein oder mehrere übersprungen werden.

Bestimme die Tränke für den höchsten Sprung.

Eingabe

• Zeile $1$: ganze Zahl $P$.
• Zeilen $2..P+1$: jede enthält eine ganze Trankstärke. Zeile 2 gibt den ersten, Zeile 3 den zweiten Trank an, und so weiter.

Ausgabe

• Zeile $1$: eine ganze Zahl, der maximal mögliche Sprung.

Beispiele

Eingabe 1

8
7
2
1
8
4
3
5
6

Ausgabe 1

17