Задача E. Шпионские страсти ≡

Условие

 — А как я узнаю связного? — поинтересовался агент 007.

 — Вот по этой купюре, — мягко улыбнулся Q, — я её разрежу замысловатым образом, одну часть отдам Вам прямо сейчас, а вторую Вам покажет наш связной при встрече. Если разрез совпадёт, можете не сомневаться — перед Вами наш разведчик.

Слышен звук разрезаемой бумаги.

 — Постойте, Q! Я хочу добавить дополнительную проверку. Пусть обе части купюры имеют одинаковую площадь.

 — Но я уже почти закончил! Даже не знаю, удастся ли мне сделать последний разрез, чтобы удовлетворить Ваше требование!

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: h и w — размер банкноты. Во второй строке через пробел расположены h − 1 натуральных чисел x_i — координаты вертикальных разрезов купюры по линиям квадратной сетки сверху вниз.

Формат выходных данных

Выведите одно натуральное число — место последнего разреза, после которого купюра распадется на две равные по площади и по высоте части. Если такой разрез сделать невозможно, выведите число -1.

Ограничения

2 ≤ h ≤ 10⁵

2 ≤ w ≤ 10⁹

1 ≤ x_i ≤ w − 1

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при h = 2, получат не менее 10 баллов.

Решения, верно работающие при w = 2, получат не менее 10 баллов.

Пояснение к примерам

В первом примере дана купюра размером 6 × 12, её площадь равна 72. Разрезы сделаны по красной линии. После последнего разреза (по зеленой линии) купюра распадется на две равные по площади части (по 36).

Во втором примере площадь купюры выражается нечетным числом единичных квадратов, разрезать её на две равные по площади части, делая разрезы по линиям квадратной сетки, невозможно.

Примеры тестов

6 12
8 9 5 7 6

1

3 5
3 3

-1