Máy bay trinh sát đang bay trên một khu vực đồi núi liên tiếp, hệ thống radar trả về một mảng gồm N cao độ của địa hình. Sở chỉ huy muốn thiết lập các chốt quan sát, và vị trí lý tưởng nhất là các "đỉnh cao", nơi mà cao độ của nó cao hơn hẳn cả vị trí ngay trước và ngay sau nó. Nhằm xác định tầm quan sát của mạng lưới, bạn hãy tính xem radar đã quét qua bao nhiêu điểm thỏa mãn điều kiện trên?

Input:

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

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

Output: Số lượng chốt quan sát có thể xây dựng.

Ví dụ:

Input:

6
1 4 3 5 2 6

Output:

2

Trong phòng thí nghiệm, hai mẫu vật thể A và B được phân tích cấu trúc sinh học thành hai chuỗi ký tự. Các nhà khoa học đang nghi ngờ vật thể B chỉ là một phiên bản biến dị của vật thể A. Điều này chỉ đúng nếu chuỗi ký tự của chúng chứa cùng một tập hợp các loại tế bào với số lượng y hệt nhau, chỉ khác về trình tự sắp xếp. Hãy lập trình để hệ thống tự động đưa ra kết luận.

Input: Hai xâu A và B trên 2 dòng (chỉ gồm chữ cái thường, độ dài <= 10^5).

Output: In ra YES nếu chúng là biến dị của nhau, NO nếu không phải.

Ví dụ:

Input:

listen
silent

Output:

YES

Tập đoàn kinh tế đang yêu cầu giám đốc tài chính báo cáo. Họ có bản ghi lợi nhuận hàng ngày của N ngày hoạt động. Hội đồng quản trị hiện đang có Q câu hỏi lạnh lùng: "Từ ngày L đến hết ngày R, tổng lợi nhuận là bao nhiêu?". Nếu dùng máy tính bỏ túi, vị giám đốc này sẽ sớm kiệt sức. Hãy viết phần mềm trả lời ngay lập tức tất cả các truy vấn của hội đồng quản trị.

Input:

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

Dòng 2: N số nguyên A1, ..., AN (|A_i| <= 10^9).

Q dòng tiếp theo: Mỗi dòng chứa L, R (1 <= L <= R <= N).

Output: Với mỗi truy vấn, in ra tổng lợi nhuận trên 1 dòng.

Ví dụ:

Input:

4 2
1 2 3 4
1 3
2 4

Output:

6
9

Trên một tiểu hành tinh được chia thành lưới tọa độ N x M, mỗi ô của lưới chứa một khối lượng khoáng sản nhất định. Chiếc xe tự hành của chúng ta được thả xuống tại vị trí trên cùng bên trái (1, 1) và nhiệm vụ là về đích tại trạm thu hồi ở góc dưới cùng bên phải (N, M). Do bộ phận chuyển động bị giới hạn sau cú hạ cánh, xe chỉ có thể di chuyển sang ô bên phải hoặc xuống ô bên dưới trong mỗi bước. Làm thế nào để mang về được khối lượng khoáng sản khổng lồ nhất?

Input:

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

N dòng tiếp theo: Mỗi dòng M số nguyên C{i, j} (0 <= C{i, j} <= 10^4).

Output: Khối lượng tài nguyên lớn nhất thu được.

Ví dụ:

Input:

3 3
1 2 3
4 5 6
7 8 9

Output:

29