#include <iostream> #include <vector> #define lg __lg using namespace std; using i64 = long long; constexpr int N = 5e5; struct Max { int operator()(int a, int b) const { return a > b ? a : b; }; }; struct Min { int operator()(int a, int b) const { return a < b ? a : b; }; }; template <class Op> struct SparseTable { int len; Op op; vector<int> table[lg(N) + 2]; SparseTable(const vector<int>& arr) : len(arr.size()) { table[0] = arr; for (int i = 0; i < lg(N) + 1; ++i) { table[i + 1].resize(len); for (int j = 0; j + (1 << i) < len; ++j) table[i + 1][j] = op(table[i][j], table[i][j + (1 << i)]); } } int query(int l, int r) const { int k = lg(r - l + 1); return op(table[k][l], table[k][r - (1 << k) + 1]); } }; struct Solution { template <class Mx, class Mn> bool check(const SparseTable<Mx>& mx, const SparseTable<Mn>& mn, int len, int diff, int k, int n) { int cnt = 0; for (int i = 0; i + len - 1 < n; ++i) { int curr = mx.query(i, i + len - 1) - mn.query(i, i + len - 1); cnt += (int)(curr >= diff); } return cnt >= k; } void solve() { int n, k; cin >> n >> k; vector<int> arr(n); for (int& x : arr) cin >> x; int len = n - k + 1; vector<int> diff; SparseTable<Max> mx(arr); SparseTable<Min> mn(arr); for (int i = 0; i + len - 1 < n; ++i) { int curr = mx.query(i, i + len - 1) - mn.query(i, i + len - 1); while (!diff.empty() && diff.back() < curr) diff.pop_back(); diff.emplace_back(curr); while (diff.size() > k) diff.pop_back(); } int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (check(mx, mn, mid, diff.back(), k, n)) r = mid; else l = mid + 1; } cout << diff.back() << ' ' << l << '\n'; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while (t-- > 0) Solution().solve(); return 0; }