← 返回题目列表

Codeforces · 1358/E

E. 你被解雇了吗?

中文机器翻译题面 查看原题

Levian 在一家大公司担任会计师。 Levian 知道公司在 $$$n$$$ 连续几个月中的每个月赚取了多少 - 在第 $$$i$$$ 个月中,公司的收入等于 $$$a_i$$$(正收入意味着利润,负收入意味着损失,零收入意味着没有变化)。由于普遍的自我隔离,前 $$$\lceil \tfrac{n}{2} \rceil$$$ 个月的收入可能完全不稳定,但随后一切都稳定下来,最后 $$$\lfloor \tfrac{n}{2} \rfloor$$$ 个月的收入是相同的。

Levian 决定告诉董事 $$$n-k+1$$$ 数字——公司连续每个 $$$k$$$ 月的总收入。换句话说,对于 $$$1$$$ 和 $$$n-k+1$$$ 之间的每个 $$$i$$$,他会说出值 $$$a_i + a_{i+1} + \ldots + a_{i + k - 1}$$$。例如,如果 $$$a=[-1, 0, 1, 2, 2]$$$ 且 $$$k=3$$$,他会说数字 $$$0, 3, 5$$$。

不幸的是,如果 Levian 报告的至少一项总收入不是利润(收入 $$$\le 0$$$),董事就会生气并解雇失败的会计师。

拯救 Levian 的职业生涯:找到任何这样的 $$$k$$$,即公司连续每个 $$$k$$$ 月都盈利,或者报告这是不可能的。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5\cdot 10^5$$$) — Levian 必须考虑的月数。

第二行包含 $$$\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$$$(如果不存在)。

如果有多个可能的答案,您可以打印任何一个。

示例

输入 #1

3
2 -1
2

输出 #1

2

输入 #2

5
2 2 -8
2

输出 #2

-1

输入 #3

6
-2 -2 6
-1

输出 #3

4

注意

在第一个示例中,$$$k=2$$$ 和 $$$k=3$$$ 满足:在第一种情况下,Levian 将报告数字 $$$1、1$$$,在第二种情况下 — 一个数字 $$$3$$$。

在第二个示例中,不存在这样的$$$k$$$。

在第三个例子中,唯一的答案是$$$k=4$$$:他将报告数字$$$1,2,3$$$。