1358_E. Are You Fired?
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 ⌈ n/2 ⌉ months income might have been completely unstable, but then everything stabilized and for the last ⌊ n/2 ⌋ 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} + … + 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 ≤ 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 ≤ n ≤ 5⋅ 10^5) — the number of months for which Levian must account.

The second line contains ⌈{n/2}⌉ integers a_1, a_2, …, a_{⌈{n/2}⌉}, where a_i (-10^9 ≤ a_i ≤ 10^9) — the income of the company in the i-th month.

Third line contains a single integer x (-10^9 ≤ x ≤ 10^9) — income in every month from ⌈{n/2}⌉ + 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.
```python
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
x = int(input())
chg = [0]

for i in range(n//2):
    chg.append(x-a[i])

for i in range(1, n//2+1):
    chg[i] += chg[i-1]

for i in range(1, n//2+1):
    chg[i] = min(chg[i], chg[i-1])

pref = sum(a)

for k in range((n+1)//2, n+1):
    if pref+chg[n-k]>0:
        print(k)
        exit()
    
    pref += x

print(-1)
```