Под ёлкой лежит N подарков в ряд. Известна радость, которую принесёт каждый подарок. По традиции Простоквашино, нельзя брать два соседних подарка — это невежливо. Дядя Фёдор хочет выбрать подарки так, чтобы суммарная радость была максимальной.
Входные данные: В первой строке число N (1 ≤ N ≤ 1000). Во второй строке N целых чисел от 1 до 1000 — радость от каждого подарка.
Выходные данные: Максимальная суммарная радость.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2 5 10 7
|
15
|