Hay \(n\) casas en línea y la \(i\)-ésima guarda \(a_i\) pesos. Un ladrón no puede entrar a dos casas vecinas (saltaría la alarma). Encuentra el mayor monto que puede juntar.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La segunda tiene los \(a_i\) \((0 \le a_i \le 10^4)\).

Salida

El mayor monto.

Ejemplo 1

Entrada

4
1 2 3 1

Salida

4

Ejemplo 2

Entrada

5
2 7 9 3 1

Salida

12

Ejemplo 3

Entrada

1
5

Salida

5