Vanya đi bộ vào ban đêm dọc theo một con đường thẳng dài có độ dài l, được thắp sáng bởi n chiếc đèn lồng. Xét hệ trục tọa độ với điểm đầu của đường phố tương ứng với điểm 0 và điểm cuối của nó tương ứng với điểm l. Khi đó đèn lồng thứ i ở điểm ai. Đèn lồng chiếu sáng tất cả các điểm trên đường phố cách nó nhiều nhất là d, trong đó d là một số dương, chung cho tất cả các đèn lồng. Vanya tự hỏi: bán kính ánh sáng tối thiểu d mà những chiếc đèn lồng phải có để thắp sáng cả con phố?

Lưu ý: Phải sắp xếp lại tọa độ theo thứ tự tăng dần

Định dạng đầu vào:

Dòng đầu tiên chứa hai số nguyên n, l (1 ≤ n ≤ 10^5, 1 ≤ l ≤ 10^9) - số lượng đèn lồng và chiều dài đường phố tương ứng. Dòng tiếp theo chứa n số nguyên ai (0 ≤ ai ≤ l). Nhiều đèn lồng có thể được đặt tại cùng một điểm. Đèn lồng có thế nằm ở cuối phố.

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

Định đạng đầu ra: In ra bán kính chiếu sáng tối thiểu, làm tròn lấy 2 chữ số sau phần thập phân

Input:

3 8
2 4 5

Output:

3.00

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

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 1 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

Ca sĩ nối tiếng Le Roi vừa nhận được các lời mời lưu diễn của n đoàn ca nhạc. Đoàn thứ i mời lưu diễn từ ngày ai đến ngày bi (ai, bi là các số nguyên, ai ≤ bi). Tuy nhiên tại một thời điểm, Le Roi chỉ có thể tham gia hát cho một đoàn duy nhất mà thôi. Với mong muốn đem lời ca tiếng hát của mình đến nhiều khán giả nhất, Le Roi quyết định sẽ chọn tham gia nhiều đoàn nhất có thể. Bạn hãy tính thử xem Le Roi nên chọn tham gia những đoàn nào để số lượng đoàn là nhiều nhất mà không bị trùng nhau về mặt thời gian.

Đầu vào:

Dòng thứ nhất là số nguyên n là số đoàn ca nhạc.

Trong n dòng tiếp theo, dòng thứ i gồm hai số ai, bi cách nhau một khoảng trắng là ngày bắt đầu và ngày kết thúc lưu diễn của đoàn thứ i.

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

Đầu ra: Số nguyên xác định số lượng đoàn nhiều nhất mà Le Roi có thể tham gia.

Input:

6
3 8
9 12
6 10
1 4
2 7
11 14

Output:

3

Priyanka làm việc cho một công ty đồ chơi quốc tế vận chuyển bằng container. Nhiệm vụ của cô là xác định cách kết hợp các đơn hàng để vận chuyển với chi phí thấp nhất. Cô ấy có một danh sách trọng lượng các món đồ. Công ty vận chuyển có yêu cầu tất cả các mặt hàng được xếp trong container phải có trọng lượng nhỏ hơn hoặc bằng 4 đơn vị cộng với trọng lượng của mặt hàng có trọng lượng nhỏ nhất. Tất cả các mặt hàng đáp ứng yêu cầu đó sẽ được vận chuyển trong một container.

Xác định số lượng container nhỏ nhất có thể được ký hợp đồng để vận chuyển các mặt hàng dựa trên danh sách trọng lượng đã cho là bao nhiêu?

Ví dụ: Có những món đồ có trọng lượng w = [1,2,3,4,5,10,11,12,13]. Điều này có thể được chia thành hai container chứa là [1,2,3,4,5] và [10,11,12,13]. Mỗi container chứa sẽ chứa các đơn hàng có trọng lượng giữa đơn hàng có trọng lượng lớn nhất và nhỏ nhất không vượt quá 4

Đầu vào:

Dòng đầu tiên chứa số nguyên là số lượng đơn hàng cần vận chuyển.

Dòng tiếp theo chứa n các số nguyên được phân tách bằng dấu cách w[1], w[2], ..., w[n] biểu thị trọng lượng của các đơn hàng.

Ràng buộc:

1 <= n <= 10^5

1 <= w[i] <= 10^4

Đầu ra: Trả về giá trị nguyên của số container Priyanka phải ký hợp đồng để vận chuyển tất cả đồ chơi.

Input:

8
1 2 3 21 7 12 14 21

Output:

4

Mark và Jane rất hạnh phúc sau khi có đứa con đầu lòng. Con trai của họ thích đồ chơi nên Mark muốn mua một ít. Có một số đồ chơi khác nhau nằm trước mặt cậu bé, được dán nhãn giá của chúng. Mark chỉ có một số tiền nhất định để chi tiêu và anh ấy muốn tối đa hóa số lượng đồ chơi mà mình mua được bằng số tiền này. Cho trước bảng giá đồ chơi và số tiền cần chi, hãy xác định số quà tối đa mà Mark có thể mua.

Đầu vào:

Dòng đầu tiên chứa hai số nguyên n và k là số lượng đồ chơi được định giá và số tiền Mark phải bỏ ra.

Dòng tiếp theo chứa n các số nguyên cách nhau bằng dấu cách là giá của từng đồ chơi

Ràng buộc:

1 <= n <= 10^5

1 <= k <= 10^9

1 <= price[i] <= 10^9

Đầu ra: In ra số lượng đồ chơi tối đa Mark có thể mua được

Input:

7 50
1 12 5 111 200 1000 10

Output:

4

Jim's Burgers có một lượng lớn khách hàng đang đói bụng. Các đơn đặt hàng có sự khác nhau về thời gian cần thiết để chuẩn bị chúng. Mỗi đơn hàng của khách có 2 giá trị là thời gian đặt hàng (thứ tự đặt hàng) và thời gian chuẩn bị.

Đầu vào:

Dòng đầu tiên chứa số nguyên là số lượng khách hàng.

Mỗi dòng tiếp theo chứa hai số nguyên được phân tách bằng dấu cách, số thứ tự và thời gian chuẩn bị cho từng đơn hàng.

Ràng buộc:

1 <= n <= 10^3

1 <= i <= n

1 <= order[i], prep[i] <= 10^6

Đầu ra: Một dòng mã số khách hàng được phân tách bằng dấu cách (hãy nhớ rằng khách hàng được đánh số từ 1 đến n) mô tả trình tự khách hàng nhận được đơn hàng. Nếu hai hoặc nhiều khách hàng nhận được đơn hàng cùng lúc, hãy in số của họ theo thứ tự tăng dần.

Input 01:

3
1 3
2 3
3 3

Output 01:

1 2 3

Input 02:

5
8 1
4 2
5 6
3 1
4 3

Output 02:

4 2 5 1 3

Lisa là bạn tin vào may mắn. Khi bạn ý làm contest thứ i trên HCNOJ bạn ý luôn có 2 giá trị L[i] và T[i] trong đó L[i] là chỉ số may mắn khi làm contest đó và T[i] là chỉ số quan trọng của contest (bằng 1 nếu contest thứ i là quan trọng và bằng 0 nếu contest thứ i là không quan trọng)

Nếu Lisa làm đúng contest thứ i thì chỉ số may mắn của bạn ý sẽ bị giảm đi 1 lượng L[i], nếu làm sai sẽ được cộng 1 lượng L[i]

Nếu Lisa làm sai không nhiều hơn k contest quan trọng thì chỉ số may mắn tối đa mà Lisa có sẽ là bao nhiêu?

Ràng buộc:

1 <= n <= 100

0 <= k <= n

1 <= Li <= 10^4

0 <= Ti <= 1

Đầu vào: Dòng đầu tiên gồm 2 số, số thứ nhất mô tả số lượng contest, số thứ 2 là k

Các dòng tiếp theo lần lượt là giá trị L[i] và T[i] của từng contest

Input:

6 3
5 1
2 1
1 1
8 1
10 0
5 0

Output:

29

Thành phố X có N thị trấn trên trục đường chính. Tọa độ của các thị trấn lần lượt là a[1],a[2], ..., a[N], các tọa độ này là phân biệt, không có 2 tọa độ nào trùng nhau. Chính quyền thành phố muốn xây dựng một tuyến buýt nhanh BRT để kết nối 2 thị trấn gần nhau nhất với nhau. Bạn hãy tính thử xem chiều dài của tuyển buýt này băng bao nhiêu? Và có bao nhiêu cặp thị trấn có tiềm năng giống nhau để xây dựng tuyến BRT này.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N (N ≤ 1000000). Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: N ≤ 1000000;-10^9 ≤ A[i] ≤ 10^9

Định dạng đầu ra: In ra 2 số nguyên C và D, lần lượt là khoảng cách ngắn nhất giữa 2 thị trấn và số lượng cặp thị trấn có cùng khoảng cách ngắn nhất này.

Input:

4
6 -3 0 4

Output:

2 1

Giải thích: Khoảng cách ngắn nhất giữa 2 thị trấn bằng 2 và có 1 cặp thị trấn thỏa mãn khoảng cách này

Số trung vị của một dãy số là số nằm ở chính giữa dãy số đó sau khi đã được sắp xếp tăng dần. Cho N là một số lẻ, hãy tìm số trung vị của dãy số.

Đầu vào:

Dòng 1: Số nguyên dương lẻ N.

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

Đầu ra:

Số trung vị tìm được.

Ràng buộc:

1 <= N <= 999 (N luôn là số lẻ)

0 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 
10 2 8 4 6

Output:

6

(Giải thích: Dãy sắp xếp là 2 4 6 8 10, số ở giữa là 6)

Ví dụ 2:

Input:

3 
100 1 50

Output:

50

Cho dãy số A gồm N phần tử. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) sao cho i < j và A[i] = A[j].

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Số lượng cặp phần tử bằng nhau.

Giới hạn:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ 1:

Input:

5 
2 1 2 2 3

Output:

3

(Giải thích: Các cặp giá trị 2 là (vị trí 0, 2), (0, 3), (2, 3))

Ví dụ 2:

Input:

3 
1 2 3

Output:

0

Một danh sách đầy đủ phải chứa các số từ 1 đến N. Tuy nhiên người ta nhập thiếu mất 1 số, nên dãy chỉ còn N-1 số. Hãy tìm số bị thiếu đó.

Dữ liệu vào:

Dòng đầu chứa số nguyên N (dãy hiện tại có N-1 số).

Dòng thứ hai chứa N-1 số nguyên, các số đều khác nhau và nằm trong khoảng [1, N].

Dữ liệu ra:

Số bị thiếu.

Giới hạn:

2 <= N <= 10^5

Ví dụ 1:

Input:

5 
1 2 4 5

Output:

3

Ví dụ 2:

Input:

4 
4 1 3

Output:

2