Vous jouez à un jeu de remplissage de grille. Sur l'interface du jeu, plusieurs cases sont disposées en ligne, et vous devez remplir chaque case avec un entier strictement positif. Le système calculera ensuite le score en fonction des nombres que vous aurez inscrits.
Avant le début de chaque manche du jeu, le système vous fournit des contraintes pour remplir les cases. Supposons qu'il y ait $n$ cases disposées en ligne pour la manche en cours : le système fournira deux entiers strictement positifs $l_i, r_i$ pour la $i$-ème case, indiquant que le nombre $x_i$ que vous inscrivez dans la $i$-ème case doit vérifier $l_i \le x_i \le r_i$. Une fois que vous avez inscrit les nombres, le système découpe la séquence de cases en plusieurs segments en séparant les cases adjacentes contenant des nombres différents. Le système calcule alors la somme des carrés des longueurs de chaque segment, ce que l'on appelle la continuité du schéma de remplissage.
Par exemple, pour le schéma de remplissage $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$, le résultat du découpage en segments est $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, et la continuité correspond à $2^2 + 2^2 + 3^2 + 2^2 = 21$.
Le but de ce jeu est de minimiser la continuité. Vous devez déterminer la valeur minimale de la continuité avec une stratégie de remplissage optimale.
Entrée
Vous devez répondre pour plusieurs manches du jeu. La première ligne contient un entier $T$ ($1 \le T \le 10^5$), représentant le nombre de manches.
Pour chaque manche du jeu :
La première ligne de l'entrée contient un entier strictement positif $n$ ($1 \le n \le 10^6$), représentant le nombre de cases.
La ligne suivante contient $n$ entiers strictement positifs $l_i$ ($1 \le l_i \le 10^9$), représentant les bornes inférieures pour chaque case.
La ligne d'après contient $n$ entiers strictement positifs $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), représentant les bornes supérieures pour chaque case.
Il est garanti que la somme totale de $n$ sur l'ensemble des manches ne dépasse pas $10^6$.
Sortie
Pour chaque manche du jeu, affichez un seul entier représentant la valeur minimale de la continuité.
Exemple
Entrée d'exemple 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
Sortie d'exemple 1
3 6 17
Remarque
Pour la première manche du jeu, un schéma de remplissage possible est $x = [3, 1, 4]$, ce qui correspond à une continuité de $1^2 + 1^2 + 1^2 = 3$.
Pour la deuxième manche du jeu, un schéma de remplissage possible est $x = [1, 2, 3, 4, 5, 6]$, ce qui correspond à une continuité de $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.
Pour la troisième manche du jeu, un schéma de remplissage possible est $x = [1, 1, 2, 2, 2, 1, 1]$, ce qui correspond à une continuité de $2^2 + 3^2 + 2^2 = 17$.