#include <iostream> #include <vector> #include <algorithm> using namespace std; // Sử dụng __int128_t để tránh tràn số (vì v*T*i có thể lên tới 10^23) typedef __int128_t int128; int N, K; long long T_long; vector<long long> X_long; // Hàm kiểm tra với vận tốc tương đối v_rel (v_rel = 2 * Speed) bool check(long long v_val) { int128 v_rel = (int128)v_val; int128 T = (int128)T_long; // Tạo mảng A với kiểu dữ liệu lớn // Công thức đúng: A[i] = X[i] - v_rel * T * i // Điều kiện hợp lệ giữa 2 điểm i, j (i < j): Xj - Xi <= v_rel * T * (j - i) // <=> Xj - v_rel * T * j <= Xi - v_rel * T * i // <=> A[j] <= A[i] vector<int128> A(N + 1); for (int i = 1; i <= N; i++) { A[i] = (int128)X_long[i] - v_rel * T * i; } int l = K; int r = K; // Block Greedy: Mở rộng ra 2 phía // A[l] đóng vai trò "nguồn cấp" (cần lớn) // A[r] đóng vai trò "nhu cầu" (cần nhỏ) // Điều kiện duy trì: A[l_effective] >= A[r_effective] while (l > 1 || r < N) { bool moved = false; // Thử mở rộng sang TRÁI if (l > 1) { int curr = l - 1; int128 min_val = A[curr]; // Tìm điểm hồi phục bên trái while (curr > 1 && A[curr] < A[l]) { if (A[curr] < min_val) min_val = A[curr]; curr--; } // Nếu tìm thấy chuỗi block trái mà điểm yếu nhất (min_val) vẫn >= A[r] // thì block này hợp lệ. if (min_val >= A[l]) min_val = A[l]; // Cập nhật lại min nếu chỉ đi 1 bước // Logic chuẩn: min_val phải lớn hơn hoặc bằng A[r] // Tuy nhiên, logic while ở trên dừng khi A[curr] >= A[l], tức là đã tìm thấy đỉnh mới. // Ta cần kiểm tra min_val của cả đoạn vừa đi qua. // Viết lại logic duyệt cho rõ ràng hơn: int next_l = l - 1; int128 current_min = A[next_l]; while (next_l > 1 && A[next_l] < A[l]) { // Đang ở thung lũng, cố đi tiếp để tìm đỉnh cao hơn next_l--; if (A[next_l] < current_min) current_min = A[next_l]; } // Kiểm tra điều kiện hợp lệ với biên phải hiện tại if (current_min >= A[r]) { l = next_l; // Nhảy cóc tới vị trí mới moved = true; } } // Thử mở rộng sang PHẢI if (r < N) { int curr = r + 1; int128 max_val = A[curr]; int next_r = r + 1; int128 current_max = A[next_r]; while (next_r < N && A[next_r] > A[r]) { // Đang ở ngọn đồi, cố đi tiếp để tìm thung lũng thấp hơn next_r++; if (A[next_r] > current_max) current_max = A[next_r]; } // Kiểm tra điều kiện hợp lệ với biên trái hiện tại if (current_max <= A[l]) { r = next_r; moved = true; } } if (!moved) return false; // Ưu tiên: Nếu cả 2 đều đi được thì sao? // Logic trên thực hiện tuần tự, nếu trái đi được thì l đã thay đổi. // Sau đó kiểm tra phải với l mới. Điều này vẫn đúng đắn (tham lam). } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); if (cin >> N >> K >> T_long) { X_long.resize(N + 1); for (int i = 1; i <= N; i++) { cin >> X_long[i]; } long long low = 0, high = 1000000000000000LL; // 10^15 long long ans = high; while (low <= high) { long long mid = low + (high - low) / 2; if (check(mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } cout << (ans + 1) / 2 << endl; } return 0; }