Este es el mas difícil de la prueba. Nunca le crean a un problema cuando diga esto.

Subtarea 1:

Hacer O(N*Q): por cada pregunta pasar por el array y el resto es trivial.

Subtarea 2:

Idea ~1-~: ~O(Q*sqrt(N)*log(N))~: Separar los elementos en intervalos de tamaño ~sqrt(N)~, ordenar estos intervalos, y pasar por ellos haciendo búsqueda binaria.

Idea 2-~: ~O(Q*(log(N)^3)): Tener un Segement Tree(ST) de vectores, tal que cada nodo contenga los elementos del intervalo ordenados y luego hacer búsqueda binaria sobre la respuesta haciendo queries en ese ~ST~.

Idea ~3-~: ~O(Q*(log(N)^3))~: Tener un ABI de vectores, tal que cada posición contenga los elementos del intervalo(que esa posición agrupa) ordenados y luego hacer búsqueda binaria sobre la respuesta haciendo queries en ese ABI.

Subtarea 3:

Idea ~1-~ ~O(Q*sqrt(N))~: Separar los elementos en intervalos de tamaño ~sqrt(N)~, normalizar los valores (compresión de coordenadas), y para cada intervalo, de tamaño ~sqrt~, sacar un array de tamaño ~N+Q~ (mayor valor de una variable luego de normalizarla) que nos diría cuantos valores hay menores o iguales que ~L~ o ~R~, y solo resta pasar por ellos.

Idea ~2-~ ~O(Q*log(N)^2)~: Basado en la Idea 2 de a subtarea anterior. Hacer Fractional Cascading. Tener en cada nodo del ST otros 4 arrays que nos dicen en el hijo izquierdo y derecho la primera posición de un elemento mayor o igual y la primera posición de un elemento mayor, entonces solo hay que hacer búsqueda binaria una vez(en el nodo ~1~) y entonces cada querie sale en ~O(log(N))~.

Idea ~3-~ ~O(Q*log(N)^2)~:Basado en la Idea 2 de a subtarea anterior. Hacer Búsqueda Binaria Implícita. Irse moviendo por el ST inteligentemente de tal forma que nos vayamos en cierta forma acercando a la respuesta, pedir ayuda si no es suficiente (la explicación esta larga).

Idea ~4-~ ~O(Q*log(N))~: Basado en la Idea 2 de la subtarea anterior. Hacer Búsqueda Binaria Implícita. Hacer Fractional Cascading.

Idea 5-O(Qlog(n)^2): Basado en la Idea 3 de la subtarea anterior. Hacer la búsqueda binaria que les ensene(a los ~11~ y ~12~), de esta forma ~log(N)~ búsquedas binarias en el ABI en total en cada querie. Esta era la solución esperada, por ser la mas sencilla de programar, incluso las demás ~O(Qlog(N)^2)~ deben ser mas lentas.