Như vậy, sau khi Hiếu thi cuối kỳ xong cũng là lúc kết thúc năm 2024. Hiếu được nhận rất nhiều lời chào tạm biệt, nhưng Hiếu không biết lời chào nào của năm 2024 hay năm nào khác. Bạn hãy giúp Hiếu kiểm tra nhé!

INPUT:

• 1 xâu ký tự s(xâu s có chứa khoảng trắng).

OUTPUT:

• In ra Yes nếu trong xâu có chuỗi 2024.
• Ngược lại, in ra No.

Sample Input

GoodBye 2024

Sample Output

Yes

Sample Input

Xin chao 2025

Sample Output

No

Đếm số chẵn lẻ

Sau khi thi OLP 2024, một thời gian dài Khang đã không động vào code. Được biết khóa mới của CLB GTLT Fithou rất giỏi. Các bạn trẻ tài năng hãy giúp anh ấy đếm số lượng các số chẵn lẻ của một mảng số nguyên

Đầu vào

• Dòng đầu tiên gồm 2 số nguyên n và t, lần lượt là số lượng phần tử trong mảng và số lượng testcase
• Dòng thứ hai gồm n phần tử của mảng
• t dòng tiếp theo mỗi dòng gồm 2 chỉ số l và r, là số lượng cần tính trong khoảng [l,r]

Đầu ra

Trên từng dòng tương ứng với mỗi t, hãy ghi số lượng số lẻ và số chẵn lần lượt theo thứ tự

Sample Input

5 2
5 3 8 12 4
1 3
3 4

Sample Output

2 1
0 2

Giới hạn

• Subtask 1 (50% số điểm): n ≤ ~1000~, t ≤ ~100~, ~1~ ≤ l ≤ r ≤ n, a_i ≤ ~10^9~
• Subtask 2 (50% số điểm): n ≤ ~2.10^5~, t ≤ ~2.10^5~, ~1~ ≤ l ≤ r ≤ n, a_i ≤ ~10^9~

Hiếu là một người yêu thích các thuật toán và thường xuyên tìm cách giải quyết các bài toán tối ưu. Hôm nay, Hiếu được cô giáo giao cho một mảng số nguyên gồm N phần tử, nhiệm vụ của Hiếu là tìm tổng lớn nhất của một dãy con liên tiếp bất kỳ trong mảng a. Một dãy con được định nghĩa là một tập hợp các phần tử liên tiếp trong mảng. Hiếu đã không thể giải bài toán này sau 2 ngày, bạn hãy giúp Hiếu nhé.

Input

Dòng đầu tiên chứ 1 số nguyên N (1 ≤ N ≤ 10⁵).
Dòng tiếp theo chứ n số nguyên a_i (-100 ≤ a_i ≤ 100).

Output

In ra tổng lớn nhất của một dãy con liên tiếp

Sample Input

5
1 2 3 -4 -5

Sample Output

6

Pháp Sư

Peter là một Pháp sư quyền năng nhưng bù lại anh ấy có 1 tính cách rất lạ. Anh ấy luôn phá hủy mọi thứ mà anh ấy nhìn thấy không vừa mắt. Một hôm khi đang đi dạo lục địa Aurion anh ấy gặp N cột đá thẳng đứng, cột thứ i có độ cao a_i m. Các cột đá này cao thấp đan xen nhau khiến Peter không thích lắm vì vậy anh ấy đã dùng phép thuật của mình để chỉnh sửa các cột đá sao cho các cột được sắp xếp theo thứ tự không giảm. Với mỗi lần thực hiện phép thuật anh ấy có thể xóa 1m độ cao của cột đá bất kì và anh ấy có thể thực hiện phép thuật vô hạn lần. Tuy mạnh là vậy nhưng Peter lại rất dốt toán, vì vậy bạn hãy giúp anh ấy tính toán tổng độ cao của các cột đá tối đa là bao nhiêu sau khi anh ấy phá hủy nó.

Ví dụ với 5 cột đá là [4, 6, 3, 8, 7] thì sau anh ấy sẽ biến nó thành [3, 3, 3, 7, 7] vậy tổng độ cao tối đa sẽ là 23.

Input

Dòng đầu tiên chứ 1 số nguyên N (1 ≤ N ≤ 1e5).
Dòng tiếp theo chứ n số nguyên a_i (1≤ a_i ≤ 1e6).

Output

In ra tổng độ cao tối đa của các cột đá sau khi biến đổi.

Sample Input

5 
4 6 3 8 7

Sample Output

23