Sau khi bán hết sách, HCN chuyển sang mở một quán cà phê.

Qua thăm dò, HCN đã biết trước ngày khai trương sẽ có n khách, khách thứ i sẽ vào thời điểm hi. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng 1 đơn vị thời gian.

Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Ví dụ, một vị khách đến ở thời điểm 5, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm 6 và tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp HCN tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input:

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương h1, h2, h3, ..., hn tương ứng với thời điểm khách đến (hi ≤ 10^5).

Output:

In ra số lượng nhân viên ít nhất cần thuê.

Input:

4
1 10 45 10

Output:

2

Cho một xâu kí tự S bao gồm các chữ cái và dấu cách, một từ được định nghĩa là các kí tự liên tiếp không chứa dấu cách, hãy sắp xếp các từ thuận nghịch khác nhau trong xâu theo thứ tự từ chiều dài tăng dần, nếu 2 từ thuận nghịch có cùng chiều dài thì từ nào xuất hiện trước sẽ được in ra trước.

Ràng buộc: ~1 \leq len(s) \leq 100000~

In ra các từ theo thứ tự sắp xếp yêu cầu, các từ được in cách nhau một dấu cách.

Input:

php aba aaaa nguyen huu hoc pop

Output:

php aba pop aaaa

Cho hai mảng A (kích thước N) và B (kích thước M). Hãy đếm số cặp (i, j) sao cho A[i] + B[j] <= K. (Gợi ý: Sort B, duyệt A và chặt nhị phân trên B).

Dữ liệu vào:

Dòng 1: Ba số nguyên N, M, K (1 <= N, M <= 10^5, |K| <= 10^9).

Dòng 2: N số nguyên A[i].

Dòng 3: M số nguyên B[j].

Dữ liệu ra:

Số lượng cặp thỏa mãn.

Ví dụ:

Input:

3 3 10 
1 5 8 
2 4 9

Output:

5

Cho mảng A gồm N số nguyên. Bạn có thể thực hiện thao tác sau nhiều lần: Chọn một số X trong mảng, nhận X điểm, sau đó xóa tất cả các phần tử có giá trị bằng X, X-1 và X+1 khỏi mảng. Hãy tìm tổng số điểm lớn nhất có thể đạt được.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên A[i] (1 <= A[i] <= 10^4).

Dữ liệu ra:

Tổng điểm lớn nhất.

Ví dụ:

Input:

3 
3 4 2

Output:

6