У Алисы есть \(n\) книг. \(1\)-я книга содержит \(a_1\) страниц, \(2\)-я книга содержит \(a_2\) страниц, \(\ldots\), \(n\)-я книга содержит \(a_n\) страниц. Алиса делает следующее:
- Она разделяет все книги на две непустые стопки. Таким образом, каждая книга оказывается ровно в одной из двух стопок.
- Алиса читает в каждой стопке одну книгу с наибольшим номером.
Алиса очень любит читать. Помогите ей найти, какое максимальное суммарное количество страниц она сможет прочитать, разделив книги на две стопки.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество страниц, которое сможет прочитать Алиса.
Примечание
В первом наборе входных данных Алиса может положить в первую стопку книгу с номером \(1\), а во вторую стопку книгу с номером \(2\). Тогда она прочитает \(a_1 + a_2 = 1 + 1 = 2\) страницы.
Во втором наборе входных данных Алиса может положить книги с номерами \(2\) и \(3\) в первую стопку, а книги с номерами \(1\) и \(4\) во вторую стопку. Тогда из первой стопки она прочитает книгу с наибольшим номером \(3\), а из второй стопки книгу с наибольшим номером \(4\). Тогда она прочитает \(a_3 + a_4 = 3 + 1 = 4\) страницы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 1
4
2 3 3 1
5
2 2 3 2 2
2
10 3
3
1 2 3
|
2
4
5
13
5
|