Wo và Row là đôi bạn cùng tiến của nhau. Cả 2 đều thuộc Đội tuyển dự thi học sinh giỏi Quốc gia của tỉnh. Họ thường thách đố nhau bằng các bài toán Tin học. Vì điểm cao hơn Wo trong đợt tuyển chọn vừa rồi, với bản tính “thích cà khịa”, thừa thắng xông lên, Row đưa ra một bài toán và đố Wo giải được. Lần này Wo quyết định không để thua Row nữa. Bài toán của Row như sau:

• Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ và số nguyên dương ~S~. Cần tìm độ dài đoạn con liên tiếp dài nhất có tổng bằng ~S~.

Bạn hãy lập trình giúp Wo tìm được lời giải tối ưu để Wo có thể giành chiến thắng trước Row nhé!

Input

• Dòng 1: số nguyên dương~N~(~1 ≤ N ≤ 10^5~) là số phần tử của dãy ~a~.
• Dòng 2:~N~số nguyên dương~a_i~(~1 ≤ i ≤ N; 1 ≤ a_i ≤ 1000~) là các phần tử của dãy ~a~.
• Dòng 3: số nguyên dương~S~.

Output

• Một số nguyên ~k~ duy nhất là độ dài đoạn con liên tiếp dài nhất có tổng bằng~S~
• Trường hợp không tìm được dãy con nào thoả mãn,in ra -1

Sample

Input #1

5
1 2 3 4 5
12

Output #1

3

Input #2

9
3 5 5 5 5 4 3 2 1
15

Output #2

5

Input #3

4
2 3 5 7
9

Output #3

-1

Hint

Ràng buộc:

• Subtask 1:30% tests có n <= 100
• Subtask 2:30% tests có n <= 3000
• Subtask 3:40% tests còn lại có n <= 100000

Giải thích:

• Ở test ví dụ 1, chỉ có dãy [3,4,5] thoả mãn nên đáp số là 3.
• Test ví dụ 2 có 3 dãy con thoả mãn là [5,5,5], [5,5,5] và [5,4,3,2,1]. Đáp số tối ưu là 5.
• Test ví dụ 3 không có dãy con liên tiếp nào có tổng bằng 9 nên đáp số là -1.

Problem source: bvquoc