E. Are You Fired?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.InputThe 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.OutputIn 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.ExamplesInput
3
2 -1
2
Output
2Input
5
2 2 -8
2
Output
-1Input
6
-2 -2 6
-1
Output
4NoteIn 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.
3
2 -1
2

2
['constructive algorithms', 'data structures', 'greedy', 'implementation', '*2400']