<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. A pair of integers <code>x</code> and <code>y</code> is called a <strong>strong</strong> pair if it satisfies the condition:</p>

<ul>
	<li><code>|x - y| &lt;= min(x, y)</code></li>
</ul>

<p>You need to select two integers from <code>nums</code> such that they form a strong pair and their bitwise <code>XOR</code> is the <strong>maximum</strong> among all strong pairs in the array.</p>

<p>Return <em>the <strong>maximum</strong> </em><code>XOR</code><em> value out of all possible strong pairs in the array</em> <code>nums</code>.</p>

<p><strong>Note</strong> that you can pick the same integer twice to form a pair.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> 7
<strong>Explanation:</strong> There are 11 strong pairs in the array <code>nums</code>: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,100]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.
</pre>

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

<pre>
<strong>Input:</strong> nums = [500,520,2500,3000]
<strong>Output:</strong> 1020
<strong>Explanation:</strong> There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2<sup>20</sup> - 1</code></li>
</ul>

class Solution:
    class Trie:
        class Node:
            def __init__(self):
                self.children = [None, None]
                self.count = 0
                self.num = None

        def __init__(self):
            self.root = self.Node()
            self.depth = -1

        def resize(self, target_len):
            if -1 < self.depth < target_len:
                for _ in range(target_len - self.depth):
                    prev_root = self.root
                    self.root = self.Node()
                    self.root.children[0] = prev_root
                    self.root.count = prev_root.count
            self.depth = max(self.depth, target_len)

        def insert(self, num):
            bin_rep = format(num, 'b')
            self.resize(len(bin_rep))
            node = self.root
            for bit in bin_rep:
                bit = int(bit)
                node.count += 1
                if not node.children[bit]:
                    node.children[bit] = self.Node()
                node = node.children[bit]
            node.count += 1
            node.num = num

        def remove(self, num):
            # it is guaranteed that num is present in Trie
            if self.root.count == 1:
                self.root = self.Node()
                self.depth = -1
                return
            bin_rep = f"{num:0{self.depth}b}"
            node = self.root
            for bit in bin_rep:
                bit = int(bit)
                node.count -= 1
                if node.children[bit] and node.children[bit].count == 1:
                    node.children[bit] = None
                    break
                node = node.children[bit]

        def search_max_xor(self, num):
            # we search num that has max bin length in trie
            bin_rep = format(num, 'b')
            self.resize(len(bin_rep))
            node = self.root
            for bit in bin_rep:
                bit = int(bit)
                node = node.children[1 - bit] if node.children[1 - bit] else node.children[bit]
            return node.num

    def maximumStrongPairXor(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        nums.sort()
        n, max_xor, trie = len(nums), 0, Solution.Trie()
        trie.insert(nums[0])
        trie_smallest_idx = 0
        for i in range(1, n):
            lower_bound = nums[i] * 0.5
            while trie_smallest_idx < n and nums[trie_smallest_idx] < lower_bound:
                trie.remove(nums[trie_smallest_idx])
                trie_smallest_idx += 1
            if trie_smallest_idx != i:
                pair = trie.search_max_xor(nums[i])
                max_xor = max(max_xor, nums[i] ^ pair)
            trie.insert(nums[i])
        return max_xor
62800