<p>The <strong>distance of a pair</strong> of integers <code>a</code> and <code>b</code> is defined as the absolute difference between <code>a</code> and <code>b</code>.</p>

<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>smallest <strong>distance among all the pairs</strong></em> <code>nums[i]</code> <em>and</em> <code>nums[j]</code> <em>where</em> <code>0 &lt;= i &lt; j &lt; nums.length</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1], k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> Here are all the pairs:
(1,3) -&gt; 2
(1,1) -&gt; 0
(3,1) -&gt; 2
Then the 1<sup>st</sup> smallest distance pair is (1,1), and its distance is 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,6,1], k = 3
<strong>Output:</strong> 5
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= n * (n - 1) / 2</code></li>
</ul>

class Solution {
public:
    int fun(vector<int>& nums, int mid){
        long long ans = 0;
        for(int i = 0; i < nums.size(); i++){
            int val = nums[i] + mid;
            int y = lower_bound(nums.begin(), nums.end(), val) - nums.begin();
            if(y == nums.size() || nums[y] > val)y--;
            long long n = y - i;
            int x = lower_bound(nums.begin(), nums.end(), val + 1) - nums.begin();
            if(x == nums.size() || nums[x] > val)x--;
            n += x - y;
            ans += n; 
           // if(mid == 2)cout<<i<<" "<<y<<" "<<nums[y]<<" "<<nums[i]<<" "<<n<<" "<<val<<endl;
           // cout<<nums[i]<<" "<<val<<" "<<y<<" "<<n<<" "<<ans<<endl;
        }
        return ans;
    }
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        for(auto i: nums)cout<<i<<' ';
        cout<<endl;
       int l = 0, r = nums.back(), ans = 0, val = 0;
       while(l <= r){
            int mid = (r - l) / 2 + l;
            int sum = fun(nums, mid);
            if(sum < k)l = mid + 1;
            else r = mid - 1, ans = mid, val = sum;
          //  cout<<l<<" * "<<r<<" * "<<val<<" * "<<mid<<" * "<<ans<<endl;
       }

       int step = 1;
       cout<<ans<<endl;
       cout<<val<<" ";
       val = val - k + 1;
       cout<<val<<endl;
      // val++;
       priority_queue<int, vector<int>, greater<int>>pq;
int res = 0, rem = 0, test = 0;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                int p = abs(nums[i] - nums[j]);
                if(p > ans)break;
              //  cout<<nums[i]<<" "<<nums[j]<<" "<<p<<" "<<test<<endl;
                if(pq.size() < val)
                    pq.push(p);
                else if(pq.top() < p){
                    pq.pop(); pq.push(p);
                }
            }
        }
       // cout<<res;
       /*while(!pq.empty()){
        cout<<pq.top(); pq.pop();
       }cout<<endl<<test<<endl;*/
        if(pq.empty())return 0;
       return pq.top();
    }
};
auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
119674