Sắp xếp

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số tăng dần (\(A_i ≤ A_{i+1}\)).

Input

• Dòng đầu chứa số \(n\),
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Một dòng chứa dãy số đã sắp xếp tăng dần.

Example

6
91 451 43 3 451 54 

3 43 54 91 451 451

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số giảm dần (\(A_i ≥ A_{i+1}\)).

Input

• Dòng đầu chứa số \(n\),
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Một dòng chứa dãy số đã sắp xếp giảm dần.

Example

6
91 451 43 3 451 54 

451 451 91 54 43 3

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số lớn thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số lớn thứ \(K\) trong dãy.

Example

6 2    
91 451 43 3 452 54 

451

Yugi có \(N\) lá bài, lá bài thứ \(i\) có sức mạnh như sau:

Nếu \(A_i \ge 0\) máu của Yugi sẽ được cộng thêm \(A_i\).

Nếu \(A_i <0\) máu của Kaiba sẽ trừ đi \(|A_i|\).

Tuy nhiên, Yugi luôn thích tấn công nên anh ta muốn trừ máu Kaiba nhiều nhất có thể.

Hãy cho biết Yugi có thể trừ Kaiba nhiều nhất là bao nhiêu khi sử dụng nhiều nhất \(m\) lá bài

Input

• Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2,…, A_n (-10000 \leq A_i \leq 10000)\).

Output

• Số máu Kaiba bị trừ.

Example

 5 3 
-6 0 35 -2 4  

8

Một dãy gồm \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) đượ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 \(a_1, a_2,..., a_n\) 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.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) (\(k < n\));
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) (a_n ≤ 10^6)

Output

• Một số nguyên là giá trị của biểu thức đạt được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^5\) và \(k = 1\);
• Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^5\);

Example

5 2
28 9 5 1 69 

100