Estás jugando a un juego de rellenar casillas. En la interfaz del juego, hay varias casillas dispuestas en una fila, y debes rellenar cada casilla con un entero positivo. Luego, el sistema calculará la puntuación en función de los números que hayas escrito.
Antes de que comience cada ronda del juego, el sistema te proporcionará restricciones para rellenar las casillas. Supongamos que hay $n$ casillas dispuestas en una fila para la partida actual; el sistema proporcionará dos enteros positivos $l_i, r_i$ para la $i$-ésima casilla, indicando que el número $x_i$ que escribas en la $i$-ésima casilla debe satisfacer $l_i \le x_i \le r_i$. Después de que hayas rellenado los números, el sistema separará la secuencia de casillas en varios segmentos basándose en las casillas adyacentes que tengan números diferentes. A continuación, el sistema calculará la suma de los cuadrados de las longitudes de cada segmento, lo que se denomina la continuidad del esquema de relleno.
Por ejemplo, para el esquema de relleno $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$, el resultado de la segmentación es $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, y la continuidad corresponde a $2^2 + 2^2 + 3^2 + 2^2 = 21$.
El objetivo de este juego es minimizar la continuidad. Debes determinar el valor mínimo de la continuidad bajo la estrategia óptima de relleno.
Entrada
Debes responder para múltiples rondas del juego. La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), que representa el número de rondas del juego.
Para cada ronda del juego:
La primera línea de la entrada contiene un entero positivo $n$ ($1 \le n \le 10^6$), que representa el número de casillas.
La siguiente línea contiene $n$ enteros positivos $l_i$ ($1 \le l_i \le 10^9$), que representan las restricciones de cota inferior para cada casilla.
La línea siguiente contiene $n$ enteros positivos $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), que representan las restricciones de cota superior para cada casilla.
Se garantiza que la suma total de $n$ en todas las partidas no supera $10^6$.
Salida
Para cada ronda del juego, imprime un único entero que represente el valor mínimo de la continuidad.
Ejemplo
Entrada de ejemplo 1
3 3 1 1 4 5 1 4 6 1 2 3 4 4 4 3 3 3 4 5 6 7 1 1 2 2 1 1 1 1 2 2 2 2 1 1
Salida de ejemplo 1
3 6 17
Nota
Para la primera ronda del juego, un posible esquema de relleno es $x = [3, 1, 4]$, que corresponde a una continuidad de $1^2 + 1^2 + 1^2 = 3$.
Para la segunda ronda del juego, un posible esquema de relleno es $x = [1, 2, 3, 4, 5, 6]$, que corresponde a una continuidad de $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.
Para la tercera ronda del juego, un posible esquema de relleno es $x = [1, 1, 2, 2, 2, 1, 1]$, que corresponde a una continuidad de $2^2 + 3^2 + 2^2 = 17$.