Cho mảng A gồm n phần tử. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất (phải thuộc mảng A) lớn hơn Ai (i = 0, 1, 2,, n-1). Đưa ra ký tự _ nếu Ai không có phần từ lớn hơn nó. Ví dụ với mảng A = (13, 6, 7, 12) ta có kết quả là (_ , 7, 12, 13).

Định dạng đầu vào: Dòng đầu tiên đưa vào n là số phần tử của mảng A; Dòng kế tiếp đưa vào n số A[i] của mảng; các số được viết cách nhau một vài khoảng trống.

Ràng buộc: 1 <= N <= 10^5; 1 ≤ A[i] <= 10^5.

Định dạng đầu ra: Đưa ra kết quả trên 1 dòng

Input:

9
6 3 9 8 10 2 1 15 7

Output:

7 6 10 9 15 3 2 _ 8

Cho số nguyên dương N rất lớn. Hãy tìm số nguyên dương K lớn nhất sao cho K * K <= N. (Không dùng hàm sqrt có sẵn, hãy dùng tìm kiếm nhị phân).

Dữ liệu vào:

Một số nguyên dương N.

Dữ liệu ra:

Số nguyên K.

Ràng buộc:

1 <= N <= 10^18

Ví dụ:

Input:

10

Output:

3

Có N cây gỗ với chiều cao khác nhau A[1], A[2], ..., A[N]. Bạn cần thu được ít nhất M mét gỗ bằng cách đặt lưỡi cưa ở độ cao H. Các phần cây cao hơn H sẽ bị cắt bỏ và bạn lấy phần đó. Hãy tìm giá trị H lớn nhất có thể để bạn lấy được ít nhất M mét gỗ.

Dữ liệu vào:

Dòng 1: N và M.

Dòng 2: N số nguyên là chiều cao các cây.

Dữ liệu ra:

Giá trị H lớn nhất (số nguyên).

Ràng buộc:

1 <= N <= 10^6

1 <= M <= 2*10^9

Chiều cao cây <= 10^9

Ví dụ:

Input:

4 7 
20 15 10 17

Output:

15

Có N đoạn dây cáp với độ dài khác nhau. Cần cắt ra K đoạn dây có độ dài bằng nhau là L. Hãy tìm giá trị L lớn nhất có thể. Kết quả làm tròn đến 2 chữ số thập phân (hoặc lấy phần nguyên tùy đề, ở đây ta lấy phần nguyên cho dễ với lớp 8).

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Độ dài N đoạn dây.

Dữ liệu ra:

Độ dài L lớn nhất (số nguyên).

Ràng buộc:

1 <= N, K <= 10^5

Độ dài <= 10^9

Ví dụ:

Input:

4 11 
802 743 457 539

Output:

200

Có N cái chuồng nằm trên một đường thẳng tại các vị trí x1, x2, ..., xN. Cần xếp C con bò vào các chuồng sao cho khoảng cách nhỏ nhất giữa 2 con bò bất kỳ là lớn nhất có thể.

Dữ liệu vào:

Dòng 1: N và C.

Dòng 2: N vị trí của các chuồng (chưa chắc đã sắp xếp).

Dữ liệu ra:

Khoảng cách lớn nhất tìm được.

Ràng buộc:

2 <= C <= N <= 10^5

0 <= xi <= 10^9

Ví dụ:

Input:

5 3 
1 2 8 4 9

Output:

3

Có N túi kẹo, túi thứ i có A[i] viên kẹo. Cần chia các túi này cho K em bé sao cho mỗi em bé nhận được một số túi kẹo LIÊN TIẾP nhau. Hãy chia sao cho tổng số kẹo lớn nhất mà một em bé nhận được là nhỏ nhất có thể (Tối thiểu hóa cái tối đa).

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Số kẹo trong các túi. Dữ liệu ra:

Tổng số kẹo lớn nhất tối thiểu. Ràng buộc:

1 <= K <= N <= 10^5

A[i] <= 10^9

Ví dụ:

Input:

5 3 
2 4 7 3 5

Output:

8