Autor: Gabriel Carmona

Tiempo límite: 2 segundos

Memoria límite: 4 megabytes

NOTA LA INUSUAL MEMORIA LÍMITE DEL PROBLEMA

¡Se abrieron las inscripciones para el Torneo Chileno de Programación (TCP)! Muchas personas se registraron para participar. Dentro de la organización está el comité de medición, en el cual trabaja Javier. Su tarea es anotar las alturas de los participantes para poder ordenarlos en la foto oficial del TCP.

Martín, encargado de acomodar a las personas en la foto, necesita consultar cuántos participantes tienen altura menor que cierta altura. Sin embargo, tiene memoria de pez dorado, así que a veces pregunta varias veces por la misma altura.

Javier, consciente de esto, quiere ayudarlo con un sistema de consultas eficiente. Pero como tiene problemas de visión, necesita que el sistema guarde todas las alturas usando poco espacio.

A último minuto, Javier se rompió las manos y no puede diseñar el sistema. Por eso te pide ayuda.

Entrada

La primera línea contiene dos enteros \(n\) y \(q\) (\(1 \le n\le 3 \cdot 10^{6}\), \(1 \le q\le 10^{6}\)), correspondiente a la cantidad de personas inscritas al TCP y la cantidad de consultas realizadas por Martín.

Le sigue una segunda línea que contiene \(n\) enteros separados por un espacio, cada entero tiene valor entre \(1\) y \(3 \cdot 10^{6}\). Cada entero corresponde a la altura de un participante. Se asegura que todas las alturas son distintas.

Finalmente, le siguen \(q\) líneas, donde cada línea contiene un entero correspondiente a la altura consultada por Martín. Cada altura consultada puede tener valor entre \(1\) y \(3 \cdot 10^{6}\).

Nota: La entrada/salida de este problema es muy grande, por lo que se recomienda usar técnicas de entrada/salida rápida.

• En C++: al inicio del programa main deberán escribir std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
• En Java: usar BufferedReader con StringTokenizer para la entrada, y BufferedWriter o PrintWriter para la salida.
• En Python: usar sys.stdin.readline en lugar de input() y sys.stdout.write para la salida.

Salida

Por cada consulta, se debe imprimir una línea con un entero, correspondiente a la cantidad de alturas menor que la altura consultada.

Ejemplos

Entrada 1

10 4
7 2 3 82 70 66 8 13 14 11
1
69
8
100

Salida 1

0
8
3
10