Codeforces Round 645 (Div. 2) |
---|
Закончено |
Левиан работает бухгалтером в большой компании. Он знает, сколько компания заработала в каждый из $$$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$$$.
Название |
---|