Codeforces Round 645 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

greedy

implementation

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Are You Fired?

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLevian works as an accountant in a large company. Levian knows how much the company has earned in each of the $$$n$$$ consecutive months — in the $$$i$$$-th month the company had income equal to $$$a_i$$$ (positive income means profit, negative income means loss, zero income means no change). Because of the general self-isolation, the first $$$\lceil \tfrac{n}{2} \rceil$$$ months income might have been completely unstable, but then everything stabilized and for the last $$$\lfloor \tfrac{n}{2} \rfloor$$$ months the income was the same.

Levian decided to tell the directors $$$n-k+1$$$ numbers — the total income of the company for each $$$k$$$ consecutive months. In other words, for each $$$i$$$ between $$$1$$$ and $$$n-k+1$$$ he will say the value $$$a_i + a_{i+1} + \ldots + a_{i + k - 1}$$$. For example, if $$$a=[-1, 0, 1, 2, 2]$$$ and $$$k=3$$$ he will say the numbers $$$0, 3, 5$$$.

Unfortunately, if at least one total income reported by Levian is not a profit (income $$$\le 0$$$), the directors will get angry and fire the failed accountant.

Save Levian's career: find any such $$$k$$$, that for each $$$k$$$ months in a row the company had made a profit, or report that it is impossible.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5\cdot 10^5$$$) — the number of months for which Levian must account.

The second line contains $$$\lceil{\frac{n}{2}}\rceil$$$ integers $$$a_1, a_2, \ldots, a_{\lceil{\frac{n}{2}}\rceil}$$$, where $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the income of the company in the $$$i$$$-th month.

Third line contains a single integer $$$x$$$ ($$$-10^9 \le x \le 10^9$$$) — income in every month from $$$\lceil{\frac{n}{2}}\rceil + 1$$$ to $$$n$$$.

Output

In a single line, print the appropriate integer $$$k$$$ or $$$-1$$$, if it does not exist.

If there are multiple possible answers, you can print any.

Examples

Input

3 2 -1 2

Output

2

Input

5 2 2 -8 2

Output

-1

Input

6 -2 -2 6 -1

Output

4

Note

In the first example, $$$k=2$$$ and $$$k=3$$$ satisfy: in the first case, Levian will report the numbers $$$1, 1$$$, and in the second case — one number $$$3$$$.

In the second example, there is no such $$$k$$$.

In the third example, the only answer is $$$k=4$$$: he will report the numbers $$$1,2,3$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 21:08:20 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|