У Юлии есть \(n\) стаканов, расположенных в линию. В \(i\)-м стакане \(a_i\) единиц сока. Юлия пьет только из стаканов с нечетными номерами, в то время как ее партнер пьет только из стаканов с четными номерами.
Чтобы произвести впечатление на своего партнера, Юлия хочет найти непрерывный подмассив этих стаканов, такой, что у Юлии и ее партнера будет одинаковое количество сока, если учитывать только стаканы в этом подмассиве. Пожалуйста, помогите ей в этом.
Формально, определите, существуют ли два индекса \(l\), \(r\) такие, что \(1 \leq l \leq r \leq n\), и \(a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}\), если \(l\) и \(r\) имеют одинаковую четность, и \(a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}\) в противном случае.
Выходные данные
Для каждого набора входных данных выведите «YES», если существует подмассив, удовлетворяющий условию, и «NO» в противном случае.
Вы можете вывести ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
В первом тесте Юлия может выбрать \(l=1\) и \(r=3\). Затем она выпьет \(a_1+a_3=1+2=3\) единиц, а ее партнер выпьет \(a_2=3\) единиц сока.
Во втором тесте Юлия может выбрать \(l=2\) и \(r=5\). Затем она выпьет \(a_3+a_5=1+1=2\) единиц, а ее партнер выпьет \(a_2+a_4=1+1=2\) единиц сока.
В третьем тесте ни один такой непрерывный подмассив не подходит.
В четвертом тесте Юлия может выбрать \(l=2\) и \(r=8\). Затем она выпьет \(a_3+a_5+a_7=11+1+1=13\) единиц, а ее партнер выпьет \(a_2+a_4+a_6+a_8=2+4+5+2=13\) единиц сока.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
1 3 2
6
1 1 1 1 1 1
10
1 6 9 8 55 3 14 2 7 2
8
1 2 11 4 1 5 1 2
6
2 6 1 5 7 8
9
2 5 10 4 4 9 6 7 8
|
YES
YES
NO
YES
NO
YES
|