Cho mảng ~A~ gồm ~N~ số nguyên dương. Sắp xếp mảng không giảm.

Hướng dẫn sort:

Input

• Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

• Sắp xếp mảng ban đầu không giảm.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên dương. Sắp xếp mảng không tăng.

Hướng dẫn sort:

Input

• Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

• Sắp xếp mảng ban đầu không tăng.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên dương. Đếm số lượng phần tử khác nhau của mảng đó và in ra các phần tử khác nhau đó theo thứ tự tăng dần.

Input

• Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

• Dòng đầu in ra ~M~ phần tử khác nhau trong mảng ~A~.
• Dòng sau in ra ~M~ số nguyên đó theo thứ tự không giảm.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên dương. Tìm số xuất hiện nhiều nhất trong dãy và số lần xuất hiện của nó.

Input

• Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

• In ra số xuất hiện nhiều nhất trong dãy và số lượng xuất hiện của số đó. Nếu 2 số có số lần xuất hiện như nhau thì in ra số bé hơn.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên dương phân biệt ~A_0, A_1, A_2, \ldots, A_{N - 1}~. Sắp xếp lại mảng ~A~ và cho biết vị trí ban đầu của mỗi giá trị (đảm bảo các giả trị là khác nhau).

Input

• Dòng đầu tiên hai số nguyên ~N~ (~1 \leq N \leq 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

• Dòng thứ nhất in ra dãy ~A~ sau khi sắp xếp không giảm.
• Dòng thứ hai in ra vị trí ban đầu của mỗi số sau khi đã sắp xếp.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên dương và mảng ~B~ gồm ~M~ số nguyên dương. Đếm số lượng phần tử giống nhau của cả hai mảng.

Input

• Dòng đầu tiên hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 5000~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).
• Dòng thứ ba chứa ~M~ số nguyên dương ~B_i~ (~B_i \leq 10^9~).

Output

• In ra số lượng phần tử giống nhau của hai tập hợp.

Sample Test

Cho mảng ~A~ gồm ~N~ số nguyên. In ra các số chẵn theo thứ tự không giảm, sau đó in ra các số lẻ theo thứ tự không giảm.

Input

• Dòng 1: chứa ~2~ số nguyên ~N~ (~N \leq 5000~).
• Dòng 2: chứa ~N~ số nguyên ~A_i \leq 10^9~.

Output

In ra yêu cầu đề bài.

Sample Test

Input:

7
2 5 6 1 3 2 3

Output:

2 2 6 1 3 3 5

Cho mảng ~A~ gồm ~N~ số nguyên. In ra số theo thứ tự: số nguyên tố từ bé đến lớn lên đầu, các số còn lại từ bé đến lớn xuống cuối.

Input

• Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i \leq 10^9~.

Output

• In ra yêu cầu đề bài.

Sample Test

Cho mảng ~A~ gồm ~n~ số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng ~A~ chỉ gồm các số nguyên liên tiếp?

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.

Output

• In ra số lượng số nguyên ít nhất phải thay.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

3
4 10 5

Output:

1

Chú ý: Thay ~10~ bằng ~6~.

Ràng buộc

• Subtask 1 ~(50\%)~: ~n \le 1000~.
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

Đây là phiên bản khó hơn của bài PA120. Điểm khác biệt duy nhất giữa hai bài là số ~k~ và giới hạn các số.

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

Qua thăm dò, TDZ đã 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 ~h_i~. Để 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 ~k~ đơ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.

Cụ thể, một vị khách đến ở thời điểm ~x~ nào đó, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~x + k~. Khách đó sẽ rời quán và nhân viên tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ 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 2 số nguyên dương ~n~, ~k~ (~n \leq 10^6, k \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^9~).

Output

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

Subtasks

• Subtask ~1~ (~25\%~): ~n \leq 10^3~.
• Subtask ~2~ (~37.5\%~): ~n \leq 10^6, h_i \leq 10^6~.
• Subtask ~3~ (~37.5\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5 2
1 2 5 3 5

Output:

2

Note: Thuê hai nhân viên:

• Nhân viên thứ nhất sẽ phục vụ khách thứ nhất, rồi đến khách thứ tư và cuối cùng phục vụ khách thứ ba.
• Nhân viên thứ hai phục vụ khách thứ hai rồi đến khách thứ năm.