Una empresa tiene ~n~ empleados con ciertos salarios. Su tarea es llevar un registro de los salarios y procesar las consultas.

Entrada

La primera línea de entrada contiene dos enteros ~n~ y ~q~: el número de empleados y consultas. Los empleados están numerados ~1,2,\ldots,n~.

La siguiente línea contiene ~n~ enteros ~p_1,p_2,\ldots,p_n~: el salario de cada empleado.

Después de esto, hay ~q~ líneas que describen las consultas. Cada línea tiene una de las siguientes formas:

• ~!~ ~k~ ~x~ : cambiar el salario del empleado ~k~ a ~x~.
• ~?~ ~a~ ~b~ : contar el número de empleados cuyo salario está entre ~a~ y ~b~.

Salida

Imprimir la respuesta a cada consulta de la forma ~?~.

Restricciones

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq p_i \leq 10^9~
• ~1 \leq k \leq n~
• ~1 \leq x \leq 10^9~
• ~1 \leq a \leq b \leq 10^9~

Ejemplo de Entrada

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Ejemplo de Salida

3
2