Hệ thống thoát nước của thành phố là một chuỗi các cột bê tông xếp liền nhau, cột thứ i có chiều cao H_i. Khi có mưa lớn, nước sẽ bị đọng lại ở những chỗ trũng giữa các cột. Bề rộng của mỗi cột là 1 đơn vị. Hãy tính tổng thể tích nước (số đơn vị nước) có thể đọng lại sau cơn mưa.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Hi (0 <= Hi <= 10^5).

Output: Tổng thể tích nước đọng lại.

Ví dụ:

Input:

12
0 1 0 2 1 0 1 3 2 1 2 1

Output:

6

(Giải thích: Nước đọng ở các vị trí có độ cao (0, 1, 0, 1, 2) lần lượt là: 0+0+1+0+1+2+1+0+0+1+0+0 = 6 đơn vị).

Trong bài kiểm tra thể chất, huấn luyện viên cần chọn ra 2 người tạo thành 1 cặp để thi đẩy tạ. Sức mạnh của người thứ i là A_i. Yêu cầu an toàn là tổng sức mạnh của 2 người trong cặp KHÔNG ĐƯỢC VƯỢT QUÁ giới hạn X. Hãy đếm xem có tất cả bao nhiêu cặp người (i, j) với i < j thỏa mãn điều kiện này.

Input:

Dòng 1: N, X (1 <= N <= 10^5, 1 <= X <= 10^9).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Số lượng cặp thỏa mãn.

Ví dụ:

Input:

5 5
1 2 3 4 5

Output:

4

Có N kiện hàng, kiện thứ i có chứa Ai sản phẩm. Máy kiểm định cần kiểm tra toàn bộ số sản phẩm này trong giới hạn H giờ. Nếu bạn cài đặt tốc độ máy là K (sản phẩm/giờ), thì kiện hàng thứ i sẽ được kiểm tra xong trong ceil(Ai / K) giờ (làm tròn lên). Máy chỉ kiểm tra từng kiện một, làm xong kiện này mới sang kiện khác (nếu 1 kiện làm xong trong 1.2 giờ thì máy vẫn mất trọn 2 giờ cho kiện đó). Hãy tìm tốc độ K nhỏ nhất để máy hoàn thành trong tối đa H giờ.

Input:

Dòng 1: N, H (1 <= N <= 10^5, N <= H <= 10^9).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Tốc độ K nhỏ nhất.

Ví dụ:

Input:

4 8
3 6 7 11

Output:

4

(Giải thích: K = 4. Kiện 3sp mất 1h. Kiện 6sp mất 2h. Kiện 7sp mất 2h. Kiện 11sp mất 3h. Tổng = 1+2+2+3 = 8 giờ. Vừa đủ H=8).

Bản đồ chiến thuật là một ma trận N x M, các ô có giá trị 0 (đầm lầy) hoặc 1 (đất cứng). Quân đội cần tìm một khu vực hình vuông (chiều dài bằng chiều rộng) hoàn toàn là đất cứng (toàn số 1) để xây dựng căn cứ. Hãy tìm diện tích của căn cứ hình vuông lớn nhất có thể xây dựng.

Input:

Dòng 1: N, M (1 <= N, M <= 1000).

N dòng tiếp theo: Mỗi dòng chứa M ký tự '0' hoặc '1' (không có khoảng trắng).

Output: Diện tích hình vuông lớn nhất.

Ví dụ:

Input:

4 5
10100
10111
11111
10010

Output:

4

(Giải thích: Có một hình vuông kích thước 2x2 toàn số 1 ở giữa ma trận, diện tích là 4).