The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 &lt;= i &lt; j &lt; a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.


	For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.


You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive).

Return an array ans where ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:


	x if x &gt;= 0.
	-x if x &lt; 0.


&nbsp;
Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.


Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 100
	1 &lt;= queries.length &lt;= 2&nbsp;* 104
	0 &lt;= li &lt; ri &lt; nums.length


class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # location of number
        loc = defaultdict(list)
        for i, num in enumerate(nums):
            loc[num].append(i)
        
        # start from sorted key thus keep tracking minimum difference
        k = sorted(loc)
        
        res = []
        for a, b in queries:
            cands = []
            ans = float('inf')
            for c in k:
                # left and right range overlap means no available locations in range
                if bisect.bisect_left(loc[c], a) == bisect.bisect(loc[c], b): continue
                if cands: 
					ans = min(ans, c - cands[-1])
                cands.append(c)
            if ans == float('inf'): ans = -1
            res.append(ans)
        return res
class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] count = new int[n + 1][100];
        int q = queries.length;
        int ans[] = new int[q];
        
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < 100; ++j)
                count[i + 1][j] = count[i][j];
            
            ++count[i + 1][nums[i] - 1];
        }
        
        for(int i = 0; i < q; ++i) {
            int low = queries[i][0];
            int high = queries[i][1] + 1;
            List<Integer> present = new ArrayList<>();
            int min = 100;
            
            for(int j = 0; j < 100; ++j)
                if(count[high][j] - count[low][j] != 0)
                    present.add(j);
            
            for(int j = 1; j < present.size(); ++j)
                min = Math.min(min, present.get(j) - present.get(j - 1));
            
            if(present.size() == 1)
                min = -1;
            
            ans[i] = min;
        }
        
        return ans;
    }
}
class Solution {
public:
    vector<bitset<101>> tree;
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();

        tree = vector<bitset<101>>(4*(n+1) + 1);
        buildtree(1, 0, n-1, nums);

        vector<int> ans;
        for(auto &e: queries){
            auto finalOnesRepresentations = query(1, 0, n-1, e[0], e[1]);

            // find the first 1
            int i = 0;
            while(i < 101 and finalOnesRepresentations[i] != 1){
                i++;
            }

            int gap = INT_MAX;
            int prev = i;
            i++;
            // find the minimum gap
            for(; i < 101; i++){
                if(finalOnesRepresentations[i] == 1){
                    gap = min(gap, i - prev);
                    prev = i;
                }
            }
            ans.push_back(gap == INT_MAX ? -1 : gap);
        }
        return ans;
    }

    bitset<101> query(int index, int s, int e, int qs, int qe){

        if(s > e) return bitset<101>();
        if(e < qs || s > qe) return bitset<101>();
        if(qs <= s and e <= qe) return tree[index];

        int mid = (s+e)/2;
        auto left = query(index*2, s, mid, qs, qe);
        auto right = query(index*2+1, mid+1, e, qs , qe);
        return left | right;
    }

    void buildtree(int index, int s, int e, vector<int>& a){

        if(s > e)return;

        if(s==e){
            bitset<101> b;
            b[a[s]] = 1;
            tree[index] = b;
            return;
        }

        int mid = (s+e)/2;
        buildtree(index*2, s, mid, a);
        buildtree(index*2+1, mid+1, e, a);
        tree[index] = tree[index*2] | tree[index*2+1];
    }
};
var minDifference = function(nums, queries) {
    const qlen   = queries.length, len = nums.length;
    const res    = new Array(qlen).fill(-1);
    const prefix = [];
    
    for(let i = 0; i <= len; i++) {
        if(i == 0) prefix[i] = new Array(101).fill(0);
        else {
            prefix[i] = Array.from(prefix[i-1]);
            prefix[i][nums[i-1]]++;   
        }
    }
    
    for(let k = 0; k < qlen; k++) {
        const [l, r] = queries[k];
        const left = prefix[l], right = prefix[r + 1];
        let prev = -1, ans = Infinity;
        for(let i = 1; i <= 100; i++) {
            const diff = right[i] - left[i];
            if(diff == 0) continue;
            
            if(prev != -1) {
                ans = Math.min(ans, i - prev);
            }
            prev = i;
        }
        if(ans != Infinity) {
            res[k] = ans;
        }
    }
    
    return res;
};
Minimum Absolute Difference Queries