Cho dãy số nguyên A gồm N phần tử A₁, A₂, ..., 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.

Dữ liệu vào

Dữ liệu được đọc từ tệp văn bản XOADOAN.INP:

- Dòng đầu tiên chứa số nguyên dương N (N ≤ 10⁵).

- Dòng thứ hai chứa N số nguyên A₁, A₂, ..., A_N (|A_i| ≤ 10⁹; 1 ≤ i ≤ N).

- Dòng thứ ba chứa số nguyên S (|S| ≤ 10¹⁴).

Kết quả

Ghi ra tệp văn bản XOADOAN.OUT: Gồm một số nguyên là kết quả của bài toán.

Ví dụ

Ví dụ 1:

Input:

5
4 -5 4 4 -2
0

Output:

2

Giải thích: Tổng dãy ban đầu là 5, cần tổng dãy nhỏ hơn hoặc bằng 0. Có thể xóa đoạn [3, 4] có tổng là 8 => tổng còn lại là 5 - 8 = -3 ≤ 0. Kết quả là 2.

Ví dụ 2:

Input:

3
4 2 1
0

Output:

3

Giải thích: Tổng dãy ban đầu là 7, cần tổng dãy nhỏ hơn hoặc bằng 0. Có thể xóa đoạn [1, 3] có tổng là 7 => tổng còn lại là 7 - 7 = 0 ≤ 0. Kết quả là 3.

Ví dụ 3:</p>

Input:

3
1 2 3
-2

Output:

-1

Giải thích: Tổng dãy ban đầu là 6, cần tổng dãy nhỏ hơn hoặc bằng -2. Không có cách xóa thỏa mãn (xóa hết thì tổng bằng 0 vẫn lớn hơn -2).