Monsieur IP est allé dans les montagnes des Carpates pour célébrer son anniversaire et a ramené un souvenir de là-bas — un constructeur ressemblant à la forme d'une montagne.
Cependant, en le transportant chez lui, certaines pièces se sont perdues, donc maintenant le constructeur se compose de segments, le -ème segment ayant une hauteur de a_i. Monsieur IP veut le faire ressembler à une montagne à nouveau pour garder les souvenirs de son anniversaire !
Il pense qu'un constructeur composé de segments de hauteurs b_1, b_2, \dots, b_n ressemble à une montagne s'il existe au moins un indice (1 \le m \le n) tel que pour chaque 1 \le i < m, b_{i} \le b_{i+1}, et pour chaque m < i \le n, b_{i-1} \ge b_{i}.
Pour faire ressembler son constructeur à une montagne, il peut effectuer l'action suivante autant de fois qu'il le souhaite :
choisir n'importe quel segment ,
choisir un entier positif (0 < x < 2^{30}), et pour un coût de pièces, changer la hauteur du segment a_j := a_j \mid x (l'explication du symbole est disponible en bas de la page).
Monsieur IP n'a pas trop de pièces, alors il se demande quel est le plus petit nombre de pièces dont il a besoin pour pouvoir faire ressembler son constructeur à une montagne à nouveau. Aidez-le à trouver ce nombre !
La première ligne de l'entrée contient un entier (1 \le t \le 5 \cdot 10^4) — le nombre de cas de test. Chaque cas de test doit être résolu indépendamment.
La première ligne de chaque cas de test contient l'entier (3 \le n \le 2 \cdot 10^5) — le nombre de segments dans le constructeur.
La deuxième ligne de chaque cas de test contient entiers a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — les hauteurs des segments.
Il est garanti que la somme des valeurs de à travers tous les cas de test ne dépasse pas 2 \cdot 10^5.
Pour chaque cas de test, sortez un entier unique — le plus petit nombre de pièces nécessaires pour faire ressembler le constructeur de Monsieur IP à une montagne.
Example 1
Le symbole représente l'opérateur "OU bit à bit".
L'OU bit à bit de deux nombres et fonctionne comme suit :
Considérez la représentation binaire de p = \overline{(p_0 p_1 \dots p_{29})}_2 et q = \overline{(q_0 q_1 \dots q_{29})}_2, où p_i, q_i \in \{0, 1\}, et p = \sum_{i=0}^{29} p_i \cdot 2^i et q = \sum_{i=0}^{29} q_i \cdot 2^i respectivement. Il peut être montré que de telles représentations sont uniques pour chaque nombre.
Le résultat de l'opération r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} est calculé comme suit :
r_i = p_i\ \textbf{ou}\ q_i, où est défini comme suit :
Premier Bit | Deuxième Bit | Bit Résultat |
Par exemple,
si p = 5 = \overline{(1010)}_2 et q = 12 = \overline{(0011)}_2, alors p \mid q = \overline{(1011)}_2 = 13;
si p = 6 = \overline{(011)}_2 et q = 7 = \overline{(111)}_2, alors p \mid q = \overline{(111)}_2 = 7.
Dans le premier cas de test, Monsieur IP peut effectuer l'opération deux fois :
choisir le segment , et pour un coût de pièces, faire a_3 := 3 \mid 4 = 7.
choisir le segment , et pour un coût de pièce, faire a_5 := 2 \mid 1 = 3.
Après cela, le constructeur ressemble à ceci : [2, 5, 7, 8, 3, 3] avec l'indice m = 4 satisfaisant a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6. Le coût total est 4+1 = 5. Il peut être montré qu'il est impossible d'atteindre l'objectif avec un coût plus faible.
Dans le deuxième cas de test, Monsieur IP peut effectuer l'opération une fois sur le segment , en payant pièces pour faire a_2 := 1 \mid 2 = 3. Aucune opération avec un coût de ne peut faire ressembler le tableau à une montagne ; par conséquent, c'est la plus petite réponse.
Dans le troisième cas, le segment avec l'indice m = 5 satisfait déjà la propriété a_1 \le a_2 \le a_3 \le a_4 \le a_5, donc aucune opération n'est nécessaire
( points): n \le 5, a_i \le 15
( points): a_i \le 2
( points): a_i \le 63
( points): n \le 100
( points): pas de restrictions supplémentaires.