Dado un árbol binario de búsqueda con valores distintos, responde consultas: para cada \(k\), el \(k\)-ésimo valor más chico del árbol (con \(k = 1\) es el mínimo).

Entrada

El árbol viene en el formato de LeetCode, en dos líneas: la primera tiene un entero \(k\) y la segunda \(k\) elementos separados por espacios, que son el recorrido por niveles del árbol. Cada elemento es el valor de un nodo o null si ese hijo no existe; los hijos de un null no se escriben y los null del final se omiten. Un árbol vacío se escribe con \(k = 0\) y una línea vacía.

Después viene \(q\) \((1 \le q \le 1002)\) y \(q\) líneas con un valor \(k\) \((1 \le k \le n)\) cada una. El árbol tiene entre \(1\) y \(2 \cdot 10^4\) nodos con valores distintos \((0 \le v \le 10^5)\) y altura a lo más \(1000\).

Salida

Para cada consulta, el \(k\)-ésimo menor valor.

Ejemplo 1

Entrada

4
3 1 4 null 2
1
1

Salida

1
1

Ejemplo 2

Entrada

8
5 3 6 2 4 null null 1
2
3
6

Salida

3
6

Basado en el problema 230 de LeetCode, Kth Smallest Element in a BST, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.