Lớp học của Minh có $n$ bạn xếp thành hàng ngang, bạn thứ $i$ có độ thông minh $a_i$. Cô giáo muốn chọn ra một nhóm gồm ba bạn đứng liên tiếp nhau trong hàng để thực hiện một nhiệm vụ học tập sao cho tổng độ thông minh của các bạn trong nhóm đạt giá trị lớn nhất.

Yêu cầu: Tìm nhóm có tổng độ thông minh lớn nhất và số cách chọn nhóm thỏa mãn yêu cầu của cô giáo.

Dữ liệu:

• Dòng đầu chứa số nguyên dương $n(2\le n\le {10}^6)$ là số học sinh trong lớp Minh;
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n,(|a_i|\le {10}^9,i=1..n)$, số thứ $i$ là độ thông minh của bạn đứng thứ $i$ trong hàng.

Kết quả:

• Ghi ra hai số nguyên dương $S,k$ trong đó $S$ là tổng độ thông minh lớn nhất của nhóm và số cách chọn nhóm thỏa mãn yêu cầu.

Ví dụ:

Sample Input

5
1 3 -2 6 3

Sample Output

7 2

Giải thích:

Trong test ví dụ: Có $2$ cách chọn nhóm có tổng độ thông minh lớn nhất là $7$ gồm $\{3,-2,6\}$ và $\{-2,6,3\}$.

Hôm nay trong tiết học toán, cô giáo giao cho các bạn trong lớp Minh bài tập thú vị về tích của các số tự nhiên như sau:

Cho số nguyên dương $n$. Hãy đếm chữ số $0$ ở tận cùng của $n!=1\times 2\times 3\times \dots \times n$.

Minh đang loay hoay tìm cách giải bài toán mà vẫn chưa làm xong. Bạn hãy giúp Minh giải bài toán này.

Dữ liệu:

• Gồm một dòng duy nhất chứa số nguyên $n(1\le n\le {10}^{18})$.

Kết quả:

• Ghi ra một số nguyên không âm duy nhất là số chữ số $0$ tận cùng của $n!$.

Ví dụ:

Sample Input

10

Sample Output

2

Giải thích:

Trong ví dụ trên: $n=10$, ta có: $10!=3628800$ có $2$ số $0$ ở tận cùng.

Ràng buộc:

• Có $40\mathrm{\%}$ số test đầu tiên có $n\le {10}^2$;
• Có $30\mathrm{\%}$ số test tiếp theo có $n\le {10}^5$;
• Có $30\mathrm{\%}$ số test còn lại $n\le {10}^{18}$.

Một xâu được gọi là mật khẩu "an toàn" nếu xâu đó thỏa mãn:

• Có độ dài ít nhất bằng $6$.
• Chứa ít nhất một chữ cái in hoa ('A'…'Z').
• Chứa ít nhất một chữ cái in thường ('a'…'z').
• Chứa ít nhất một chữ số ('0'…'9').

Ví dụ: "a1B2C3","tinHoc6" là hai mật khẩu "an toàn", còn "a1B2C", "a1b2c3", "A1B2C3", "tinHoc" đều không là mật khẩu "an toàn".

Một lần, Minh nhìn thấy một xâu $S$ có độ dài $n(n\le {10}^6)$ chỉ gồm các loại kí tự: chữ cái in hoa, chữ cái in thường và chữ số. Minh muốn đếm xem có bao nhiêu cặp chỉ số $(i,j)$ thỏa mãn hai điều kiện:

• $1\le i<j\le n.$
• Xâu con gồm các ký tự liên tiếp từ $i$ đến $j$ là mật khẩu "an toàn".

Yêu cầu: Bạn hãy giúp Minh tính số lượng cặp $(i,j)$ thỏa mãn điều kiện nêu trên.

Dữ liệu vào:

• Gồm một dòng duy nhất chứa duy nhất xâu $S$.

Kết quả:

• Ghi ra một số nguyên không âm là kết quả tìm được.

Ví dụ:

Sample Input

abc3456789PQ

Sample Output

6

Giải thích:

Trong ví dụ trên có $6$ mật khẩu "an toàn" là: "c3456789P", "c3456789PQ", "bc3456789P", "bc3456789PQ", "abc3456789P", "abc3456789PQ".

Ràng buộc:

• Có $40\mathrm{\%}$ số điểm ứng với các test có $n\le {10}^2$.
• Có $30\mathrm{\%}$ số điểm ứng với các test có $n\le {10}^3$.
• Có $30\mathrm{\%}$ số điểm ứng với các test còn lại có $n\le {10}^6$.

Có $n$ quyển sách đánh số từ $1$ đến $n$ được bày trên giá sách nằm ngang, quyển thứ $i$ có giá $x_i$ đồng. Trong túi Bờm có tổng cộng $K$ đồng và muốn mua một số quyển sách liên tiếp nhau sao cho không vượt quá số tiền hiện có.

Yêu cầu: Bạn hãy giúp Bờm, đếm số cách mua sách thỏa mãn yêu cầu của bạn ấy nhé.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương $n,K(n\le {10}^6,K\le {10}^9)$ là số quyển sách và tổng số tiền Bờm có;
• Dòng thứ hai chứa n số nguyên $x_1,x_2,\dots ,x_n$ trong đó số $x_i$ là giá tiền quyển sách thứ $i$ ($1\le x_i\le {10}^6,x_1+x_2+\dots +x_n\le {10}^9$).

Kết quả:

• Ghi ra một số nguyên không âm duy nhất là số cách mua thỏa mãn yêu cầu của Bờm.

Ví dụ:

Sample Input

5  4
1 5 1 2 3

Sample Output

5

Giải thích:

Trong test ví dụ: Có $5$ quyển sách, Bờm có $4$ đồng. Bờm có các cách mua sách như sau:

• Cách $1$: Mua quyển $1$.
• Cách $2$: Mua quyển $3$.
• Cách $3$: Mua quyển $3,4$.
• Cách $4$: Mua quyển $4$.
• Cách $5$: Mua quyển $5$.

Ràng buộc:

• Có $30\mathrm{\%}$ số test có $n\le {10}^2$;
• Có $30\mathrm{\%}$ số test tiếp theo có ${10}^2<n\le {10}^3$;
• Có $40\mathrm{\%}$ số test cuối cùng có ${10}^3<n\le {10}^6$.

Trên đại lộ Bắc Nam có $n$ cây cổ thụ. Tính từ Bắc vào Nam, cây thứ $i$ có chiều cao $h_i$. Nhân dịp đầu năm mới, người dân muốn chọn ra một số cây, ngọn của hai cây liên tiếp được chọn sẽ được nối bằng đoạn dây đèn nháy lung linh. Tuy nhiên, vì yêu cầu đặc biệt về mỹ quan, Ban quản lý đường muốn rằng khi đi từ đầu đến cuối con đường (hướng Bắc vào Nam), sẽ luôn thấy dây đèn cao lên, hay nói cách khác, các đỉnh cây được chọn có chiều cao tăng dần từ đầu con đường.

Yêu cầu: Cho $n$ và dãy số nguyên dương $h_1,h_2,..,h_n$. Hãy xác định số lượng cây tối đa có thể chọn dùng để mắc đèn trang trí.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương $n(n\le {10}^5)$;
• Dòng thứ $2$ chứa $n$ số nguyên không âm $h_1,h_2,h_3,\dots ,h_n$.

Kết quả:

• Ghi ra một số duy nhất là số lượng cây tối đa tìm được.

Ví dụ:

Sample Input

6
2 9 4 6 2 7

Sample Output

4

Ràng buộc:

• Có $40\mathrm{\%}$ số test khác tương ứng $40\mathrm{\%}$ số điểm có $n\le {10}^5,h_i\le {10}^6$;
• Có $40\mathrm{\%}$ số test tương ứng với $40\mathrm{\%}$ số điểm có $n\le {10}^3,h_i\le {10}^6$;
• Có $20\mathrm{\%}$ số test còn lại tương ứng $20\mathrm{\%}$ số điểm có $n\le {10}^5,h_i\le {10}^9$.