Multiset is enough.

i think min suffix array will work

Let the size of the array be len.

So, for the 0th index, it can club to all the indices from n to len-1. Maintain a multiset for that and then find the lower and upper bound of the A[i] and maintain the answer. After every iteration remove the A[i+n] element from the multiset.

Sorry for my bad English.

similar leetcode problem

If you choose some number, then it's best pair is either the minimum element that it can pair with or the maximum. Now start from the $$$n$$$'th element. It can pair up with element $$$0$$$. Element $$$n+1$$$ can pair with $$$0$$$ and $$$1$$$, $$$n+2$$$ with $$$0$$$, $$$1$$$ and $$$2$$$, ... . Now you can just hold the minimum and maximum for that prefix and update the answer as necessary. Time complexity $$$O(N)$$$ where $$$N$$$ is the size of the array, auxilary memory $$$O(n)$$$ where $$$n$$$ is the number in the problem.

I rename k the thing you call "n" in the problem description. I assume k <= n (n is the size of the array in the code below).

You can go from L to R and keep track in a set of pair of {val, idx}. As soon as the loop index i is i >= k you start look backward in the array. The goal is to find the already seen number so that it is as close as possible to a[i] and has an index j<=i-k. I did this thing with binary search lower bound. When doing lower bound you either find and element greater than a[i] or equal. So if you find equal the answer is 0 and you are done, if you find a greater one, you go one step below with the set iterator and check also this case to be compared with the current a[i]. When doing binary search on set of pair i look for the pair {a[i], -inf} which basically is I want the index as small as possible, but this part smells a bit, maybe there is a better way.

I leave a code snippet. Maybe its buggy, but I am pretty sure about the idea. Also there is most likely a better way of retrieving this element than doing lower bound, but I don't know such a method, if somebody knows I would be pleased to know it.

	ll n, k; cin >> n >> k;
	vector<ll> a(n);
	for(ll i = 0; i < n; ++i){
		cin >> a[i];
	}
	
	//assume k <= n
	//got from left to right and for each a[i] look for the best answer
	//achivable looking backward (already seen elements which distance at least k from i)
	
	const ll inf = 1e17;
	set<pair<ll, ll>> seen;	
	ll ans = inf;
	for(ll i = 0; i < n; ++i){
		if(i - k >= 0) {
			auto x = seen.lower_bound(mp(a[i], -inf));
			if(x == seen.end()){
				x--;
			}
			ll idx_hi = (*x).second;
			ll p1 = (i - idx_hi >= k) ? abs(a[i] - (*x).first) : inf;
			ans = min(ans, p1);
			if(x != seen.begin()){
				x--;
				ll idx_lo = (*x).second;
				ll p2 = (i - idx_lo >= k) ? abs(a[i] - (*x).first) : inf;
				ans = min(ans, p2);
			}
		}
		seen.insert(mp(a[i], i));
	}
	cout << ans << "\n";

[Deleted maybe my approach was wrong]

Well maybe this can work for you, I reworded the problem and used the solve function for at least 'k' indexes apart. First we preset the map from kth index onwards in the array as preprocessing and initialize r = k and l = 0. In a loop can find the lower and upper bound for each element and check from their differences to update the answer, we delete element from the r-th index next as it's no longer valid next iteration and erase it from the map if it's frequency becomes 0, and we also add the l-th index element if it's valid next iteration (increment l along with it), increment r and move on solving it. This approach uses Two Pointers and Ordered Maps, hope this helps:

#include<bits/stdc++.h>
using namespace std;
//Absolute difference returner
int Adiff(int a,int b){
    if((a - b) > 0) return a - b;
    return b - a;
}
//Solving for least absolute difference assuming 'k' indices apart
int solve(int n, int k, vector<int>& nums){
    map<int,int> mp;
    //pre-setting values into map
    for(int i=k;i<n;i++) mp[nums[i]]++;
    //2-Pointer approach
    int l = 0, r = k, ans = INT_MAX;
    for(int i=0;i<n;i++){
        /*checking for upper & lower bounded elements as they
        can both lead to the answers from both sides*/
        auto it1 = mp.lower_bound(nums[i]);
        auto it2 = mp.upper_bound(nums[i]);
        //update ans to which one has lower absolute difference
        ans = min(ans,min(Adiff((*it1).first,nums[i]),Adiff((*it2).first,nums[i])));
        mp[nums[r]]--;
        if(mp[nums[r]]==0) mp.erase(nums[r]); //erasing element from right that's no longer valid
        if((i + 1 - l) >= k){ //Adding element from left if it's going to be valid for next iteration
            mp[nums[l]]++;
            l++; //Increment l for next iteration
        }
        r++; //increment r for next deletion
    }
    return ans;
}
int main(){
    //Test cases for solving function
    int t;
    cin >> t;
    while(t--){
        int n, k, x;
        vector<int> nums;
        cin >> n >> k;
        for(int i=0;i<n;i++){
            cin >> x;
            nums.push_back(x);
        }
        cout << solve(n,k,nums) << "\n";
    }
    return 0;
}
/*
For solve() function:
Time Complexity: O(N*log(N))
Space Complexity: O(N)
*/