<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>

template <bool ReverseSortOrder = false>
class Treap {
public:
    ~Treap() {
        clean(root);
    }

    int size() const {
        return sub_tree_size(root);
    }

    void insert(int val) {
        root = insert(root, val);
    }

    void remove(int val) {
        root = remove(root, val).first;
    }

    // idx -> (value, pref sum)
    std::pair<int, long long> get(int idx) const {
        return get(root, sub_tree_size(root->left), sub_tree_sum(root->left), idx);
    }

    int rank(int val) const {
        if (root == nullptr) {
            return 0;
        }
        return rank(root, sub_tree_size(root->left), val);
    }

    int height() const {
        return height(root);
    }

    std::vector<int> values() const {
        std::vector<int> data;
        data.reserve(size());
        data.clear();
        values(root, data);
        return data;
    }

private:
    struct Node {
        int priority;
        int value;
        int value_count;
        int sub_tree_size;
        long long sub_tree_sum;
        Node* left;
        Node* right;
    };

    void clean(Node* node) {
        if (node == nullptr) {
            return;
        }
        clean(node->left);
        clean(node->right);
        delete node;
    }

    static int gen_prio() {
        static std::mt19937 random_engine(std::random_device{}());
        static std::uniform_int_distribution<int> random_dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
        return random_dist(random_engine);
    }

    static int sub_tree_size(const Node* node) {
        return node ? node->sub_tree_size : 0;
    }

    static long long sub_tree_sum(const Node* node) {
        return node ? node->sub_tree_sum : 0;
    }

    static long long node_value_sum(const Node* node) {
        return node ? (long long) node->value_count * node->value : 0;
    }

    static void fixup(Node* node) {
        node->sub_tree_size = sub_tree_size(node->left) + sub_tree_size(node->right) + node->value_count;
        node->sub_tree_sum = sub_tree_sum(node->left) + sub_tree_sum(node->right) + node_value_sum(node);
    }

    std::pair<int, long long> get(const Node* node, int node_idx, long long less_sum, int target_idx) const {
        if (target_idx >= node_idx && target_idx < node_idx + node->value_count) {
            return {node->value, less_sum + (target_idx - node_idx + 1) * (long long) node->value};
        }
        if (target_idx < node_idx) {
            const int next_idx = node_idx - sub_tree_size(node->left->right) - node->left->value_count;
            const long long next_less_sum = less_sum - sub_tree_sum(node->left->right) - node_value_sum(node->left);
            return get(node->left, next_idx, next_less_sum, target_idx);
        } else {
            const int next_idx = node_idx + node->value_count + sub_tree_size(node->right->left);
            const long long next_less_sum = less_sum + node_value_sum(node) + sub_tree_sum(node->right->left);
            return get(node->right, next_idx, next_less_sum, target_idx);
        }
    }

    int rank(const Node* node, int node_idx, int val) const {
        if (val < node->value) {
            if (node->left == nullptr) {
                return node_idx;
            }
            const int next_idx = node_idx - sub_tree_size(node->left->right) - node->left->value_count;
            return rank(node->left, next_idx, val);
        } else if (val > node->value) {
            if (node->right == nullptr) {
                return node_idx + node->value_count;
            }
            const int next_idx = node_idx + node->value_count + sub_tree_size(node->right->left);
            return rank(node->right, next_idx, val);
        } else {
            return node_idx;
        }
    }

    Node* rotate_left(Node* node) {
        Node* new_parent = node->right;
        node->right = new_parent->left;
        fixup(node);
        new_parent->left = node;
        fixup(new_parent);
        return new_parent;
    }

    Node* rotate_right(Node* node) {
        Node* new_parent = node->left;
        node->left = new_parent->right;
        fixup(node);
        new_parent->right = node;
        fixup(new_parent);
        return new_parent;
    }

    static bool less(int a, int b) {
        if constexpr (ReverseSortOrder) {
            return b < a;
        }
        return a < b;
    }

    Node* insert(Node* node, int val) {
        if (node == nullptr) {
            Node* new_node = new Node();
            new_node->priority = gen_prio();
            new_node->value = val;
            new_node->value_count = 1;
            new_node->left = nullptr;
            new_node->right = nullptr;
            fixup(new_node);
            return new_node;
        }
        if (less(val, node->value)) {
            node->left = insert(node->left, val);
        } else if (less(node->value, val)) {
            node->right = insert(node->right, val);
        } else {
            ++node->value_count;
            fixup(node);
            return node;
        }
        fixup(node);
        if (less(val, node->value)) {
            if (node->priority > node->left->priority) {
                node = rotate_right(node);
            }
        } else {
            if (node->priority > node->right->priority) {
                node = rotate_left(node);
            }
        }
        return node;
    }

    std::pair<Node*, bool> remove(Node* node, int val) {
        if (node == nullptr) {
            return {nullptr, false};
        }
        bool deleted;
        if (val == node->value) {
            if (node->value_count > 1) {
                --node->value_count;
                fixup(node);
                return {node, true};
            }
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                return {nullptr, true};
            }
            if (node->left == nullptr || (node->right != nullptr && node->left->priority > node->right->priority)) {
                node = rotate_left(node);
                std::tie(node->left, deleted) = remove(node->left, val);
            } else {
                node = rotate_right(node);
                std::tie(node->right, deleted) = remove(node->right, val);
            }
        } else if (less(val, node->value)) {
            std::tie(node->left, deleted) = remove(node->left, val);
        } else {
            std::tie(node->right, deleted) = remove(node->right, val);
        }
        if (deleted) {
            fixup(node);
        }
        return {node, deleted};
    }

    int height(const Node* node) const {
        if (node == nullptr) {
            return 0;
        }
        return std::max(height(node->left), height(node->right)) + 1;
    }

    void values(const Node* node, std::vector<int>& data) const {
        if (node == nullptr) {
            return;
        }
        values(node->left, data);
        data.insert(data.end(), node->value_count, node->value);
        values(node->right, data);
    }

    Node* root = nullptr;
};

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        const int sz = nums.size();
        const int max_val = *max_element(nums.begin(), nums.end());
        auto get_diff_cnt_less_k = [&](int target) {
            if (target == 0) {
                return 0;
            }
            Treap sorted_set;
            int cnt = 0;
            for (int i = sz - 1; i >= 0; --i) {
                cnt += sorted_set.rank(nums[i] + target) - sorted_set.rank(nums[i] - target + 1);
                sorted_set.insert(nums[i]);
            }
            return cnt;
        };
        int l = 1;
        int r = max_val;
        while (l < r) {
            const int m = midpoint(l, r);
            const int diff_cnt = get_diff_cnt_less_k(m);
            if (diff_cnt < k) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l - 1;
    }
};
59160