Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, ..., A_N\) và số nguyên \(S\). Bạn có thể xóa đi một đoạn con liên tiếp bất kỳ trong dãy (tức là chọn hai chỉ số \(L, R\) với \(1 \leq L \leq R \leq N\) và xóa các phần tử \(A_L, A_{L+1}, ..., A_R\)). Quy ước: Nếu xóa hết dãy thì tổng còn lại bằng \(0\).

Yêu cầu: Tìm độ dài nhỏ nhất của đoạn con cần xóa sao cho tổng các phần tử còn lại của dãy không vượt quá \(S\). Nếu không cần xóa đoạn nào thì kết quả là \(0\), nếu không có cách xóa thỏa mãn thì kết quả là \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^5; 1 \leq i \leq N)\)
• Dòng thứ ba chứa số nguyên \(S\) \((|S| \leq 10^{14})\)

Output

• Gồm một số nguyên là kết quả của bài toán

Example

5
4 -5 4 4 -2
0

2

3
4 2 1
0

3

3
1 2 3
-2

-1

3
1 2 0
5

0

Scoring

• \(40\%\) số test ứng với \(40\%\) số điểm có \(N \leq 100; A_i \geq 0\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(N \leq 5000; A_i \geq 0\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm có \(A_i \geq 0\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm