E. Вы уволены?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Левиан работает бухгалтером в большой компании. Он знает, сколько компания заработала в каждый из $$$n$$$ подряд идущих месяцев — в $$$i$$$-й месяц у компании доход был равен $$$a_i$$$ (положительный доход означает прибыль, отрицательный доход означает убыль, нулевой доход означает отсутствие изменений). Из-за всеобщей самоизоляции, первые $$$\lceil \tfrac{n}{2} \rceil$$$ месяцев доход мог быть совершенно нестабилен, но потом всё стабилизировалось и последние $$$\lfloor \tfrac{n}{2} \rfloor$$$ месяцев доход был одинаковый.

Левиан решил, что на совете директоров сообщит $$$n-k+1$$$ число — суммарный доход компании за каждые $$$k$$$ подряд идущих месяцев. Формально, для всех $$$i$$$ от $$$1$$$ до $$$n-k+1$$$ он скажет число $$$a_i + a_{i+1} + \ldots + a_{i + k - 1}$$$. Например, если $$$a=[-1, 0, 1, 2, 2]$$$ и $$$k=3$$$, то он сообщит числа $$$0, 3, 5$$$.

К большому сожалению, если хоть один суммарный доход, сообщаемый Левианом, не является прибылью (то есть доход $$$\le 0$$$), то начальство разозлится и уволит не справившегося с работой бухгалтера.

Спасите карьеру Левиана: найдите такое число $$$k$$$, что за любые $$$k$$$ подряд идущих месяцев компания получила прибыль или скажите, что это невозможно.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 5\cdot 10^5$$$) — количество месяцев, за которые Левиан должен отчитаться.

Вторая строка содержит $$$\lceil{\frac{n}{2}}\rceil$$$ целых чисел $$$a_1, a_2, \ldots, a_{\lceil{\frac{n}{2}}\rceil}$$$, где $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — доход компании в $$$i$$$-м месяце.

Третья строка содержит одно целое число $$$x$$$ ($$$-10^9 \le x \le 10^9$$$)— доход в каждый месяц с $$$\lceil{\frac{n}{2}}\rceil + 1$$$ до $$$n$$$.

Выходные данные

В единственной строке выведите искомое число $$$k$$$ или $$$-1$$$, если его не существует. Если существует несколько возможных решений, выведите любое из них.

Примеры
Входные данные
3
2 -1
2
Выходные данные
2
Входные данные
5
2 2 -8
2
Выходные данные
-1
Входные данные
6
-2 -2 6
-1
Выходные данные
4
Примечание

В первом примере подходят $$$k=2$$$ и $$$k=3$$$: в первом случае Левиан сообщит числа $$$1, 1$$$ а во втором — одно число $$$3$$$.

Во втором примере ни одно $$$k$$$ не подходит.

В третьем примере ответом является только $$$k=4$$$: он сообщит числа $$$1,2,3$$$.