E. Are You Fired?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Levian 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$$$.