Xóa đoạn

Cho dãy số nguyên $A$ gồm $N$ phần tử $A_1,A_2,\dots ,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},\dots ,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 (tổng cả dãy đã không vượt quá $S$) thì kết quả là $0$; nếu không có cách xóa nào thỏa mãn thì kết quả là $-1$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $N$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$.
• Dòng thứ ba chứa số nguyên $S$.

Dữ liệu ra

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

Ràng buộc

• $1\le N\le {10}^5$.
• $|A_i|\le {10}^9$.
• $|S|\le {10}^{14}$.

Subtasks

• $40\%$ số test ứng với $40\%$ số điểm: $N\le 100$, $A_i\ge 0$.
• $20\%$ số test tiếp theo ứng với $20\%$ số điểm: $N\le 5000$, $A_i\ge 0$.
• $20\%$ số test tiếp theo ứng với $20\%$ số điểm: $A_i\ge 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.

Ví dụ