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 ≤ L ≤ R ≤ 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 ≤ 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| ≤ 10^9~; ~1 ≤ i ≤ N~).
• Dòng thứ ba chứa số nguyên ~S~ (~|S| ≤ 10^{14}~).

Output

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

Sample Input 1

5
4 -5 4 4 -2
0

Sample Output 1

2

Sample Input 2

3
4 2 1
0

Sample Output 2

3

Sample Input 3

3
1 2 3
-2

Sample Output 3

-1

Sample Input 4

3
1 2 0
5

Sample Output 4

0

Subtasks

• Có 40% số test ứng với 40% số điểm có ~N ≤ 100~; ~A_i ≥ 0~.
• 20% số test tiếp theo ứng với 20% số điểm có ~N ≤ 5000~; ~A_i ≥ 0~.
• 20% số test tiếp theo ứng với 20% số điểm có ~A_i ≥ 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.