As vacas de Farmer John querem saltar sobre a Lua como na cantiga infantil favorita. Infelizmente não conseguem saltar.

O feiticeiro local preparou $P$ poções ($1 \le P \le 150{,}000$) para ajudá-las. Devem ser tomadas exatamente na ordem de criação, mas algumas podem ser ignoradas.

Cada poção tem «força» ($1 \le strength \le 500$) que melhora o salto. Tomá-la num passo ímpar aumenta o salto; num passo par diminui. Antes das poções, a capacidade de salto é naturalmente 0.

Nenhuma poção pode ser tomada duas vezes. Depois de começar, deve-se tomar uma por passo a partir do tempo 1. Uma ou mais podem ser ignoradas a cada turno.

Determine quais poções tomar para o salto mais alto.

Entrada

• Linha $1$: inteiro $P$.
• Linhas $2..P+1$: cada uma contém um inteiro, a força de uma poção. A linha 2 dá a primeira, a 3 a segunda, e assim por diante.

Saída

• Linha $1$: um inteiro, o salto máximo possível.

Exemplos

Entrada 1

8
7
2
1
8
4
3
5
6

Saída 1

17