Tom có một số nguyên dương \(n\) và dãy số nguyên \(a_{1},a_{2},\ldots,a_{n}\). Ở mỗi thao tác Tom có thể xóa một số ở đầu hoặc cuối dãy.

Yêu cầu: Hãy cho biết Tom cần thực hiện ít nhất bao nhiêu thao tác để tổng các số còn lại đúng bằng \(k\).

Dữ liệu vào:

+ Dòng đầu tiên ghi hai số \(n,k\ (1 \leq n \leq {2.10}^{6};0 \leq k \leq 10^{9})\)

+ Dòng thứ hai ghi lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (0 \leq a_{i} \leq 1000;i = 1\ldots n)\)

Dữ liệu vào luôn đảm bảo có kết quả.

Kết quả:

+ Một số nguyên cho biết kết quả của bài toán.

Ràng buộc:

+ Có 20% số test có \(k = 0\);

+ Có 20% số test khác có \(1 \leq n \leq 100;\)

+ Có 20% số test khác có \(1 \leq n \leq 2000;\)

+ Có 20% số test khác có \(1 \leq n \leq {2.10}^{5}\)

+ Có 20% số test còn lại không có ràng buộc gì thêm

Ví dụ:

Giải thích ví dụ: Thao tác ít nhất là xóa 1 số bên trái và 2 số bên phải.