Un arreglo de \(n\) enteros distintos estaba ordenado de menor a mayor, pero fue rotado: se tomó un prefijo (quizás vacío) y se movió al final. Por ejemplo, 0 1 2 4 5 6 7 puede quedar como 4 5 6 7 0 1 2.

Responde \(q\) consultas: para cada valor \(x\), su posición en el arreglo rotado o \(-1\) si no está. Cada consulta debe 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 rotado \((|a_i| \le 10^9)\) y la tercera los \(q\) valores \(x\) \((|x| \le 10^9)\).

Salida

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

Ejemplo 1

Entrada

7 3
4 5 6 7 0 1 2
0 3 7

Salida

4
-1
3

Ejemplo 2

Entrada

1 2
1
0 1

Salida

-1
0

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