Estás jugando a un juego de rompecabezas que cuenta con $n$ piedras preciosas en una fila, numeradas del 1 al $n$ de izquierda a derecha. La $i$-ésima piedra preciosa tiene el color $c[i]$.
En cualquier momento, puedes seleccionar dos piedras preciosas adyacentes del mismo color y eliminarlas. Luego, las piedras preciosas a ambos lados se deslizan para cerrar el hueco, lo que posiblemente cree nuevos pares adyacentes.
Se te darán $q$ escenarios independientes. En el $j$-ésimo escenario, solo considerarás las piedras preciosas que comienzan desde la piedra $l[j]$ y terminan en la piedra $r[j]$. Suponiendo que realizas una secuencia óptima de eliminaciones, ¿cuál es el número mínimo de piedras preciosas que pueden quedar atrás?
Entrada
Tu programa debe leer desde la entrada estándar.
La primera línea de la entrada contiene dos enteros separados por espacios $n$ y $q$.
La segunda línea de la entrada contiene $n$ enteros separados por espacios $c[1], c[2], \dots, c[n]$.
Las siguientes $q$ líneas de la entrada contienen cada una dos enteros separados por espacios. La $i$-ésima de estas líneas contiene $l[i]$ y $r[i]$.
Salida
Tu programa debe imprimir a la salida estándar.
La salida debe contener $q$ líneas. La $i$-ésima de estas líneas debe contener un entero, la respuesta para el $i$-ésimo escenario.
Restricciones
Para todos los casos de prueba, la entrada satisfará los siguientes límites:
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ para todo $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ para todo $1 \le j \le q$
Tu programa será probado en instancias de entrada que satisfagan las siguientes restricciones:
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 0 | 0 | Casos de prueba de ejemplo |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | Las piedras preciosas del mismo color forman un subarreglo contiguo (Si $c[i] = c[j]$ y $i < j$, entonces $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$ para todo $1 \le j \le q$ |
| 5 | 8 | Hay exactamente dos piedras preciosas de cada color |
| 6 | 16 | $c[i] \le 2$ para todo $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | Sin restricciones adicionales |
Ejemplos
Entrada 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
Salida 1
1 0 1 4
Nota 1
Este caso de prueba es válido para las subtareas 3, 7, 8 y 9.
Entrada 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
Salida 2
2 0 0
Nota 2
Este caso de prueba es válido para las subtareas 3, 6, 7, 8 y 9.
Explicación de los ejemplos
Explicación del ejemplo 1
Las $n = 8$ piedras preciosas se muestran en el diagrama a continuación.
Figura 1. Proceso de eliminación de piedras preciosas
En el primer escenario, solo se deben considerar las primeras tres piedras preciosas. Eliminar cualquier par de piedras adyacentes dejará exactamente una piedra atrás, después de lo cual es imposible eliminar más piedras. Por lo tanto, la respuesta es 1.
En el segundo escenario, las piedras preciosas pueden eliminarse de la siguiente manera, sin dejar ninguna atrás:
En el tercer escenario, las piedras preciosas pueden eliminarse de la siguiente manera, dejando una atrás:
En el cuarto escenario, no se puede eliminar ninguna piedra preciosa. Por lo tanto, la respuesta es 4.