Le mucche di Farmer John vogliono saltare sopra la Luna come nella loro filastrocca preferita. Purtroppo non possono saltare.

Lo stregone locale ha preparato $P$ pozioni ($1 \le P \le 150{,}000$) per aiutarle. Vanno prese esattamente nell’ordine di creazione, ma alcune possono essere saltate.

Ogni pozione ha una «forza» ($1 \le strength \le 500$) che migliora il salto. Prenderla in un passo dispari aumenta il salto; in uno pari lo diminuisce. Prima delle pozioni, la capacità di salto è naturalmente 0.

Nessuna può essere presa due volte. Una volta iniziato, se ne deve prendere una a ogni passo dal tempo 1. Si possono saltare una o più pozioni a ogni turno.

Determina quali pozioni prendere per il salto più alto.

Input

• Riga $1$: intero $P$.
• Righe $2..P+1$: ognuna contiene un intero, la forza di una pozione. La riga 2 dà la prima, la 3 la seconda, e così via.

Output

• Riga $1$: un intero, il massimo salto possibile.

Esempi

Input 1

8
7
2
1
8
4
3
5
6

Output 1

17