Есть \(n\) конфет разложенных слева направо на столе, конфеты пронумерованы слева направо. Вес \(i\)-й конфеты равняется \(w_i\). Алиса и Боб едят конфеты.
Алиса может съесть любое количество конфет слева (она ест их подряд и не может пропускать конфеты).
Боб может съесть любое количество конфет справа (он ест их подряд и не может пропускать конфеты).
Если Алиса съела конфету, то Боб уже не сможет её съесть (и наоборот).
Они хотят поделить конфеты честно. Поэтому суммарные веса съеденных ими конфет должны быть равны. Какое наибольшее суммарное количество конфет они могут съесть в таком случае?
Выходные данные
Для каждого набора выведите единственное число — максимальное количество, которое могут съесть Алиса и Боб, соблюдая условие.
Примечание
В первом примере Алиса съест одну конфету слева, а Боб съест одну конфету справа. Нет лучшего способа съесть набор конфет одинакового веса. Ответ \(2\), так как они съедят суммарно две конфеты.
Во втором примере Алиса съест первые три конфеты слева (суммарным весом \(7\)), а Боб съест первые три конфеты справа (суммарным весом \(7\)). Они не могут съесть больше конфет, так как все конфеты съедены. Ответ равен \(6\), так как они съели суммарно шесть конфет.
В третьем примере Алиса и Боб не могут съесть наборы конфет одинакового ненулевого веса, поэтому ответ равен \(0\).
В четвертом примере Алиса съест конфеты весом \([7, 3, 20]\), а Боб съест конфеты весом \([10, 8, 11, 1]\), каждый из них съест набор конфет суммарным весом \(30\). Лучшего способа съесть конфеты нет, поэтому ответ \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
10 20 10
6
2 1 4 2 4 1
5
1 2 4 8 16
9
7 3 20 5 15 1 11 8 10
|
2
6
0
7
|