Bài tập

Có \(n\) lớp học được đăng ký để sử dụng một phòng học chung. Lớp thứ \(i\) có thời gian bắt đầu \(l_i\) và thời gian kết thúc \(r_i\), tức là lớp này sẽ sử dụng phòng từ thời điểm \(l_i\) đến \(r_i\) (tính cả hai đầu).

Do hạn chế cơ sở vật chất, tại mọi thời điểm, tối đa chỉ có \(k\) lớp được phép diễn ra trong cùng một phòng. Hãy loại bỏ ít lớp nhất có thể để đảm bảo rằng điều kiện này được thỏa mãn.

\InputFile

• Dòng đầu chứa hai số nguyên \(n\) và \(k\) (\(1 \le k \le n \le 2\cdot 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(1 \le l_i \le r_i \le 2\cdot 10^5\)) --- mô tả thời gian của lớp học thứ \(i\).

\OutputFile

• Một dòng duy nhất in ra số nguyên \(m\) --- số lớp học tối thiểu cần loại bỏ.

\Scoring

• Subtask 1 (25%): \(n \le 20\).
• Subtask 2 (25%): \(n \le 5000\).
• Subtask 3 (50%): không có ràng buộc gì thêm.

Example

3 1
1 3
1 2
3 3

1

Vương quốc Byteland có \(N\) nút giao thông trọng điểm được đánh số từ \(1\) đến \(N\). Hệ thống đường cao tốc gồm \(M\) con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) nối nút giao thông \(X_i\) với \(Y_i\) (\(1 \le i \le M, 1 \le X_i, Y_i \le N\)) có phí đường bộ là \(Z_i\) (\(Z_i \le 10^6\)).

\begincenter

\endcenter

Ví dụ: Từ nút giao thông 1 đến nút giao thông 4 (như hình vẽ) có hai đường đi khác nhau: đường đi thứ nhất là \(1 \to 2 \to 4\) có tổng phí đường bộ là 30, đường đi thứ hai là \(1 \to 3 \to 4\) có tổng phí đường bộ là 35.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa \(K\) con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông \(S\) đến nút giao thông \(T\) sau khi được Quốc vương ban hành chính sách mới.

Input

• Dòng đầu ghi năm số nguyên dương \(N, M, K, S, T\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi ba số nguyên dương \(X_i, Y_i, Z_i\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Example

4 4 1 1 4
1 2 10
1 3 30
2 4 20
3 4 5

5 

Scoring

• Có 20% số điểm tương ứng \(1 < N, M \le 100000\) và \(K = 0\);
• Có 20% số điểm tương ứng \(1 < N \le 100, M \le 1000\) và \(K = 1\);
• Có 20% số điểm tương ứng với \(1 < N, M \le 100000\) và \(K = 1\);
• Có 40% số điểm tương ứng với \(100 < N, M \le 100000\) và \(1 < K \le 10\).

Linh là một học sinh rất yêu thích lập trình. Gần đây, Linh đang phát triển một robot có thể phân tích chuỗi số và tìm các đoạn "dễ thương".

Cụ thể, một đoạn con liên tiếp \((l, r)\) của dãy \(A_1, A_2, \ldots, A_n\) được gọi là dễ thương nếu:

• \(max - min = k\), với \(max\) là giá trị lớn nhất và \(min\) là giá trị nhỏ nhất trong đoạn đó.

Linh muốn bạn giúp đếm xem trong dãy ban đầu có tất cả bao nhiêu đoạn con dễ thương.

\InputFile

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le n \le 5 \times 10^5\), \(0 \le k \le 10^9\)).
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(-10^9 \le A_i \le 10^9\)).

\OutputFile

In ra một số nguyên duy nhất --- số lượng đoạn con dễ thương trong dãy.

\Scoring

• Subtask 1 (40% số điểm): \(n \le 10^3\).
• Subtask 2 (30% số điểm): \(n \le 10^5\).
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 1 3 3

6

Có một bãi đỗ xe hình vòng tròn gồm \(n\) chỗ trống, được đánh số từ \(1\) đến \(n\).
Có \(n\) chiếc xe lần lượt đi vào bãi để đỗ.

Chiếc xe thứ \(i\) muốn đỗ ở vị trí \(p_i\).
Nếu vị trí đó đã bị chiếm, xe sẽ tiếp tục di chuyển theo chiều tăng của chỉ số (theo vòng tròn) cho đến khi gặp chỗ trống đầu tiên, rồi dừng lại ở đó.

Yêu cầu: Xác định vị trí mà mỗi xe sẽ đỗ.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 5 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \ldots, p_n\) \((1 \le p_i \le n)\).

\OutputFile

• In ra \(n\) số nguyên. Số thứ \(i\) là vị trí bãi đỗ của chiếc xe thứ \(i\).

\Scoring

• Có \(40\%\) số điểm ứng với \(n \le 1000\).

Example

3
2 2 2

2 3 1