Stai giocando a un gioco di riempimento di una griglia. Sull'interfaccia di gioco sono disposte diverse caselle in fila, e devi riempire ciascuna casella con un intero positivo. Il sistema calcolerà poi il punteggio in base ai numeri che hai inserito.
Prima dell'inizio di ogni turno di gioco, il sistema ti fornirà dei vincoli per riempire le caselle. Supponendo che ci siano $n$ caselle disposte in fila per la partita corrente, il sistema fornirà due interi positivi $l_i, r_i$ per l'$i$-esima casella, indicando che il numero $x_i$ che inserisci nell'$i$-esima casella deve soddisfare $l_i \le x_i \le r_i$. Dopo che avrai inserito i numeri, il sistema suddividerà la sequenza di caselle in diversi segmenti separando le caselle adiacenti con numeri diversi. Il sistema calcolerà quindi la somma dei quadrati delle lunghezze di ciascun segmento, chiamata continuità dello schema di riempimento.
Ad esempio, per lo schema di riempimento $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$, il risultato della segmentazione è $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, e la continuità corrisponde a $2^2 + 2^2 + 3^2 + 2^2 = 21$.
L'obiettivo di questo gioco è minimizzare la continuità. Devi determinare il valore minimo della continuità seguendo la strategia di riempimento ottimale.
Input
Devi rispondere per più turni di gioco. La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), che rappresenta il numero di turni di gioco.
Per ciascun turno di gioco:
La prima riga di input contiene un intero positivo $n$ ($1 \le n \le 10^6$), che rappresenta il numero di caselle.
La riga successiva contiene $n$ interi positivi $l_i$ ($1 \le l_i \le 10^9$), che rappresentano i vincoli di limite inferiore per ciascuna casella.
La riga seguente contiene $n$ interi positivi $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), che rappresentano i vincoli di limite superiore per ciascuna casella.
È garantito che la somma totale di $n$ su tutte le partite non superi $10^6$.
Output
Per ciascun turno di gioco, stampa un singolo intero che rappresenta il valore minimo della continuità.
Esempio
Input di esempio 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
Output di esempio 1
3 6 17
Nota
Per il primo turno di gioco, un possibile schema di riempimento è $x = [3, 1, 4]$, che corrisponde a una continuità di $1^2 + 1^2 + 1^2 = 3$.
Per il secondo turno di gioco, un possibile schema di riempimento è $x = [1, 2, 3, 4, 5, 6]$, che corrisponde a una continuità di $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.
Per il terzo turno di gioco, un possibile schema di riempimento è $x = [1, 1, 2, 2, 2, 1, 1]$, che corrisponde a una continuità di $2^2 + 3^2 + 2^2 = 17$.