Một xâu nhị phân ~S~. Ta có thể thao tác trên xâu này bằng cách:

• Chọn 1 số ~p~ bất kì ~(1 \le n)~
• Chặt xâu ~S~ đang xét ra thành 2 xâu con ~S_x[1 ... p]~, ~S_y[p + 1 ... n]~
• Lặp lại các thao tác trên các xâu con được tạo ra

Chú ý: ~n~ là độ dài của xâu ~S~ hiện tại

Một xâu nhị phân được định nghĩa là Hoàn Hảo khi và chỉ khi tất cả các số 0 đến đứng sau số 1

Yêu Cầu: Hãy đếm số lần biến đổi nhỏ nhất để biến đổi xâu ~S~ thành một xâu Hoàn Hảo.

INPUT

• Gồm một dòng là xâu ~S~ ~(|S| \le 10^7)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~|S| \le 100~
• Subtask 2 (80%): ~|S| \le 10^7~

SAMPLE

Input

1000111011

Output

3

Explanation

Ta chọn các số x lần lượt là:

x = 7: 1000111|011

x = 4: 1000|111|011

x = 1: 1|000|111|011

-> Sắp xếp lại: 000|011|111|1

-> Thỏa mãn yêu cầu đề bài

Trong cuộc thi THT vừa rồi, Tèo đã đạt được giải khá cao, vượt chỉ tiêu mà Tèo và thầy đội tuyển đặt ra.

Nên thầy quyết định cho Tèo quyền chọn ra một số món quà cho bản thân mình.

Thầy đội tuyển chuẩn bị ~n~ món quà được đánh số từ ~1~ đến ~n~, phần thưởng thứ ~i~ ~(i \le n)~ sẽ có giá trị là ~a_i~.

Vì thầy đội tuyển đâu có ngu mà cho Tèo chọn hết. Nên thầy sẽ đưa ra một luật lệ rằng:

• Tèo không thể chọn quá 2 món quà liên tiếp nhau.

Nhưng Tèo cũng đâu phải dạng tép riu đâu. Vừa tài năng vừa tham lam nên Tèo trong một vài giây tính toán đã biết được tổng ~S~ lớn nhất mà mình có thể nhận được.

Tuy tính toán nhanh là vậy, nhưng Tèo lại không quá tin vào kết quả của mình.

Nên Tèo muốn nhờ bạn viết một chương trình kiểm tra xem tổng ~S~ lớn nhất của dãy ~a_i~ ~(i \le n)~ có thể tạo ra là bao nhiêu. Từ đó cậu có thể so sánh với kết quả của mình.

Lưu ý: ~S~ là tổng giá trị của các mòn quà được chọn.

Yêu Cầu: Tìm tổng ~S~ lớn nhất.

INPUT

• Dòng đầu số nguyên dương ~n~ ~(n \le 10^5)~
• Dòng tiếp theo là dãy nguyên dương ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^{6})~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~n \le 20~
• Subtask 2 (50%): ~n \le 10^4~
• Subtask 3 (30%): ~n \le 10^5~

SAMPLE

Input

5
5 4 1 3 4

Output

16

Explanation

Các món quà ta có thể chọn để đạt được Smax là:

S = a[1] + a[2] + a[4] + a[5]
  = 5 + 4 + 3 + 4
  = 16

Cho một xâu ~S~, hãy đếm số cách tạo xâu "skibidi" trong xâu ~S~

Yêu cầu: In ra số cách tạo xâu "skibidi" trong xâu ~S~

NOTE: Vì kết quả có thể rất lớn nên hãy in kết quả sau khi chia dư cho ~10^9 + 7~

INPUT

• Gồm một dòng là xâu ~S~ ~(|S| \le 10^5)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (50%): ~|S| \le 100~
• Subtask 2 (50%): ~|S| \le 10^5~

SAMPLE

Input

abskxyibzzzicccdiii

Output

3

Shinoz cho bạn một dãy ~A~ gồm ~n~ phần tử và muốn bạn hãy sắp xếp mảng lại thành một mảng không giảm.

Nhưng Shinoz lại thấy bài toán này khá là đơn giản nên cậu ta sẽ cho bạn biến đổi mảng ~A~ như sau:

• Chọn 2 chỉ số ~i~ và ~j~ ~(1 \le i < j \le n)~

• Xóa 2 phần tử ~A_i~ và ~A_j~

• Chèn vào mảng tổng của ~A_i~ và ~A_j~ ở vị trí bất kì

Hãy lặp lại thao tác này cho đến khi dãy ~A~ ban đầu trở thành dãy không giảm.

Yêu cầu: Hãy đếm số lần biến đổi nhỏ nhất để mảng ~A~ trở thành mảng không giảm

INPUT

• Dòng đầu chứa số ~n~ ~(1 \le n \le 2.10^5)~
• Dòng tiếp là dãy ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^6)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (30%): ~n \le 10^4~
• Subtask 2 (70%): ~n \le 2.10^5~

SAMPLE

Input

5
1 3 2 2 5

Output

1

Explanation

- Ta chọn i = 2 và j = 3

- Xóa A[2] và A[3]

- Chèn vào cuối mảng tổng của A[2] + A[3] = 3 + 2 = 5

-> Mảng sau khi biến đổi: 1 2 5 5

-> Thỏa mãn yêu cầu bài toán là biến đổi thành dãy không giảm

-> Chỉ tốn 1 lần biến đổi

Cho trước dãy ~A~ gồm ~n~ phần tử và ~k~ thao tác. Bạn có thể thao tác trên dãy này bằng cách:

• Chọn 1 số ~i~ bất kì ~(i \le n)~
• Bỏ ~A_i~ vào mảng ~T~
• Xóa số thứ ~i~ khỏi dãy ~A~

Chú ý: Gọi ~S~ là tích của mọi phần tử của mảng ~T~ được tạo ra sau ~k~ thao tác

Yêu cầu: Cho biết số số ~0~ tận cùng lớn nhất của tích ~S~.

INPUT

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~ ~(n \le 200, k \le n)~
• Dòng tiếp theo là dãy nguyên dương ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^{18})~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~n \le 20, A_i \le 10^3~
• Subtask 2 (80%): ~n \le 200~

SAMPLE

Input

3 2
10 6 9

Output

1

Input

4 3
75 36 17 23

Output

2

Explanation

Test thứ 1:

Mảng T = [10, 6]
-> S = 60 
-> ans = 1

Test thứ 2:

Mảng T = [75, 36, 23]
-> S = 62100
-> ans = 2