Xóa đoạn

Cho dãy số nguyên $A$ gồm $N$ phần tử $A_1, A_2, \ldots, 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 \le L \le R \le N$ và xóa các phần tử $A_L, A_{L+1}, \ldots, 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 từ file văn bản XOADOAN.INP:

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

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

• Có 40% số test ứng với 40% số điểm có $N \le 100;\ A_i \ge 0$.
• 20% số test tiếp theo ứng với 20% số điểm có $N \le 5000;\ A_i \ge 0$.
• 20% số test tiếp theo ứng với 20% số điểm có $A_i \ge 0$.
• 20% số test tiếp theo ứng với 20% số điểm không có ràng buộc gì thêm.