human
What is a Python program to print the value that is in the index $pos_j$ of the optimal subsequence of the given sequence $a$ for $k=k_j$ given the following:
I found an interesting problem on https://codeforces.com/problemset/problem/1227/D2:
This is the harder version of the problem. In this version, $1 \le n, m \le 2\cdot10^5$. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems.

You are given a sequence of integers $a=[a_1,a_2,\dots,a_n]$ of length $n$. Its subsequence is obtained by removing zero or more elements from the sequence $a$ (they do not necessarily go consecutively). For example, for the sequence $a=[11,20,11,33,11,20,11]$:  $[11,20,11,33,11,20,11]$, $[11,20,11,33,11,20]$, $[11,11,11,11]$, $[20]$, $[33,20]$ are subsequences (these are just some of the long list).
 $[40]$, $[33,33]$, $[33,20,20]$, $[20,20,11,11]$ are not subsequences. 

Suppose that an additional non-negative integer $k$ ($1 \le k \le n$) is given, then the subsequence is called optimal if:  it has a length of $k$ and the sum of its elements is the maximum possible among all subsequences of length $k$.
 and among all subsequences of length $k$ that satisfy the previous item, it is lexicographically minimal. 

Recall that the sequence $b=[b_1, b_2, \dots, b_k]$ is lexicographically smaller than the sequence $c=[c_1, c_2, \dots, c_k]$ if the first element (from the left) in which they differ less in the sequence $b$ than in $c$. Formally: there exists $t$ ($1 \le t \le k$) such that $b_1=c_1$, $b_2=c_2$, ..., $b_{t-1}=c_{t-1}$ and at the same time $b_t<c_t$. For example:  $[10, 20, 20]$ lexicographically less than $[10, 21, 1]$,  $[7, 99, 99]$ is lexicographically less than $[10, 21, 1]$,  $[10, 21, 0]$ is lexicographically less than $[10, 21, 1]$. 

You are given a sequence of $a=[a_1,a_2,\dots,a_n]$ and $m$ requests, each consisting of two numbers $k_j$ and $pos_j$ ($1 \le k \le n$, $1 \le pos_j \le k_j$). For each query, print the value that is in the index $pos_j$ of the optimal subsequence of the given sequence $a$ for $k=k_j$.

For example, if $n=4$, $a=[10,20,30,20]$, $k_j=2$, then the optimal subsequence is $[20,30]$ — it is the minimum lexicographically among all subsequences of length $2$ with...

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is Python program to print the value that is in the index $pos_j$ of the optimal subsequence of the given sequence $a$ for $k=k_j$.

import sys

class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1

class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                   ...