Một dãy gồm n số nguyên không âm a1, a2,...., an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trằng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1 +69 là biểu thức có giá trị lớn nhất. Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2..., an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Đầu vào: Dòng đầu chứa hai số nguyên dương n, k; Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an;

Ràng buộc: 1 <= k < n ≤ 10^5; 0 <= a[i] ≤ 10^6

In ra giá trị lớn nhất của biểu thức

Input:

5 3
10 1 3 9 8

Output:

29

Cho một xâu S gồm các chữ cái in thường, tìm xâu con liên tiếp dài nhất mà không có ký tự nào bị lặp lại, nếu có nhiều xâu con thỏa mãn thì in ra xâu con cuối cùng. Ví dụ xâu S = "abcaaaabcda" thì xâu con "bcda" là xâu con dài nhất mà không có ký tự nào bị lặp lại.

Ràng buộc: ~0 < len(S) \leq 10^6~

Input 01:

dabacdadbbdd

Output 01:

bacd

Input 02:

abcaaadabcda

Output 02:

bcda

Giải thích: Xâu con dài nhất cuối cùng không có ký tự nào bị lặp lại là xâu bcda

Ta gọi một cặp số (x, y) là tương tự nhau nếu chúng có cùng tính chất chẵn lẻ hoặc có abs(x - y) = 1. Bạn được cung cặp một mảng A[] có N phần tử, hãy kiểm tra xem có thể chia N phần tử này thành các cặp, sao cho mỗi cặp số đều tương tự nhau.

Đầu vào: Dòng đầu tiên chứa số nguyên dương N là số chẵn. Dòng 2 chứa N số nguyên của mảng A[]

Ràng buộc: 1 <= N <= 100; 1 <= A[i] <= 1000

Đầu ra: In ra YES nếu có thể chia thành các cặp tương tự, ngược lại in ra NO

Input:

6
78 17 17 42 11 43

Output:

YES