Nhập vào một mảng A gồm N số nguyên. In ra các bước của thuật toán sắp xếp đổi chỗ trực tiếp.

Ràng buộc: ~0 < N \leq 10^6~, ~-10^6 \leq A[i] \leq 10^6~

Input:

4
5 7 3 2

Output:

Buoc 1: 2 5 7 3 
Buoc 2: 2 3 5 7 
Buoc 3: 2 3 5 7

Xây dựng chương trình nhập vào một mảng các số thực (kiểu double) D gồm N phần tử, sau đó sắp xếp mảng đó theo thứ tự giảm dần.

Ràng buộc ~0 < N \leq 10^6~, ~-10^6 \leq D[i] \leq 10^6~

Input:

5
1.3 0.8 7.2 6.7 2.5

Output:

7.2 6.7 2.5 1.3 0.8

Cho mảng gồm n số nguyên. Hãy sắp xếp các phần tử theo thứ tự tăng dần và in ra kết quả.

Input:

Dòng 1: số nguyên n (1 ≤ n ≤ 1000).

Dòng 2: n số nguyên.

Output:

Một dòng gồm n số nguyên đã được sắp xếp.

Ví dụ:

Input:

5
3 1 4 1 5

Output:

1 1 3 4 5

Cho mảng gồm n số nguyên. Hãy sắp xếp các phần tử theo thứ tự giảm dần và in ra kết quả.

Input:

Dòng 1: số nguyên n (1 ≤ n ≤ 1000).

Dòng 2: n số nguyên.

Output:

Một dòng gồm n số nguyên đã được sắp xếp giảm dần.

Ví dụ:

Input:

4
9 2 7 5

Output:

9 7 5 2

Đại học Bang Berland đang tổ chức một buổi khiêu vũ trong lễ kỷ niệm 100500 năm thành lập! n các chàng trai và m cô gái đã bận rộn luyện tập các động tác nhảy múa. Cho biết rằng một số cặp nam và nữ sẽ được mời tham dự vũ hội. Tuy nhiên, kỹ năng khiêu vũ của các đối tác trong mỗi cặp khác nhau nhiều nhất là một đơn vị. Đối với mỗi chàng trai, chúng tôi biết kỹ năng nhảy của cậu ấy. Tương tự, đối với mỗi cô gái, chúng tôi biết kỹ năng khiêu vũ của cô ấy. Viết mã xác định số cặp lớn nhất có thế được hình thành từ n trai và m gái.

Định dạng đầu vào: Dòng đầu tiên chứa số nguyên n và m (1 <= n, m ≤ 10^5) - số chàng trai và số cô gái.

Dòng thứ hai chứa dãy a1, a2, ... , an (1 ≤ ai ≤ 10^5), trong đó ai là kỹ năng nhảy của chàng trai thứ i.

Dòng thứ ba chứa dãy b1, b2, ..., bm (1 ≤ bj ≤ 10^5), trong đó bj là kỹ năng nhảy của cô gái thứ j.

Ràng buộc: 1 <= n, m <= 10^5; 0 ≤ ai ≤ 10^5; 0 ≤ bj ≤ 10^5

Định dạng đầu ra: In một số duy nhất - số cặp tối đa được yêu cầu.

Input:

2 3
1 2
2 3 4

Output:

2

Phân tích nhóm (phân nhóm, chia nhóm) là công việc phân chia các phần tứ trong một tập hợp thành một hoặc nhiều nhóm mà trong đó các phần tử trong cùng một nhóm sẽ giống nhau hơn so với phần tử thuộc nhóm khác. Cho một tập N số nguyên dương và một sổ nguyên dương K, nhiệm vụ của bạn là đểm xem có bao nhiêu nhóm. Biết rắng 2 phần tử được xếp chung nhóm với nhau nếu như chênh lệch giữa chúng không vượt quá K. Ví dụ: với tập N = 7 số nguyên dương: 2, 6, 1, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau: 2 và 1 chung một nhóm (chênh lệch giữa chúng là 1, không vượt quá K) 2 và 3 chung một nhóm 6 và 7 chung một nhóm 3 và 4 chung một nhóm Vậy ta sẽ có 3 nhóm: {1, 2, 3, 4}, {6, 7} và (9}

Đầu vào:

Dòng đầu chứa 2 số nguyên dương N, K;

Dòng thứ hai chứa N số nguyên dương - các phần tử của tập hợp

Ràng buộc: 1<=N<=10^5; 1<=K<=10^6; Các phần tử trong tập hợp là số nguyên có trị tuyệt đối không vượt quá 10^6

Đầu ra: Kết quả của bài toán

Input:

7 1
2 6 1 7 3 4 9

Output:

3

Vào một buổi sáng anh Bo sắp xếp một đàn bò gôm n con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ có khả năng sẽ vắt được ai lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 01 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng.... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Đầu vào:

Dòng thứ nhất là số nguyên là số lượng con bò.

Dòng thứ hai gồm n số nguyên a1, a2...., an là sản lượng sữa của các con bò.

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

Số nguyên xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Input

4
4 4 4 4

Output:

10

Nam có n viên gạch được đánh số từ 1 đến n. Các viên gạch có độ cứng lần lượt là a1, a2,..., an. Một viên gạch có độ cứng x nghĩa là Nam có thể chồng lên trên viên gạch đó tối đa x viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó bị vỡ. Hỏi Nam có thể sắp được chồng gạch cao nhất là bao nhiêu?

Đầu vào:

Dòng đầu tiên là số nguyên n - là số viên gạch.

Dòng tiếp theo gồm n số nguyên a1, a2,.... an mỗi số cách nhau một khoảng trắng.

Ràng buộc: 1<=n<=10^5; 0 <= ai <= 10^6

Input:

4
1 2 3 4

Output:

4

Cho một mảng các số nguyên gồm N phần tử. Tìm khoảng cách (độ chênh lệch) nhỏ nhất của 2 phần tử bất kỳ trong mảng.

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~1 \leq A[i] \leq 10^9~

input:

5
1 2 7 5 6

Output:

1

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 mảng các số nguyên gồm N phần tử. Đếm số lượng các số khác nhau trong mảng

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~1 \leq A[i] \leq 10^9~

input:

10
1 2 2 1 3 4 3 5 6 7

Output:

7