Tienes un arreglo \(a\) de \(n\) enteros distintos ordenado de menor a mayor, y \(q\) consultas. En cada consulta te dan un valor \(x\): responde la posición de \(x\) en el arreglo, o \(-1\) si no está.

Cada consulta tiene que responderse en \(O(\log n)\).

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene el arreglo \((|a_i| \le 10^9)\) y la tercera los \(q\) valores consultados \((|x| \le 10^9 + 1)\).

Salida

Para cada consulta, una línea con la posición de \(x\) (contada desde \(0\)) o \(-1\).

Ejemplo 1

Entrada

6 2
-1 0 3 5 9 12
9 2

Salida

4
-1

Ejemplo 2

Entrada

1 3
5
5 4 6

Salida

0
-1
-1

Basado en el problema 704 de LeetCode, Binary Search, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.