Гори#522

Гори

2 секунди
512 мегабайтів
Дуже складна

Містер IP поїхав до Карпатських гір, щоб відсвяткувати свій день народження, і приніс звідти сувенір — конструктор, що нагадує форму гори.

Однак, під час перенесення додому, деякі частини загубилися, тому тепер конструктор складається з частин, причому -та частина має висоту a_i. Містер IP хоче знову зробити його схожим на гору, щоб зберегти спогади про свій день народження!

Він вважає, що конструктор, що складається з частин висот b_1, b_2, \dots, b_n, виглядає як гора, якщо існує хоча б один індекс (1 \le m \le n) такий, що для кожного 1 \le i < m, b_{i} \le b_{i+1}, і для кожного m < i \le n, b_{i-1} \ge b_{i}.

Щоб зробити свій конструктор схожим на гору, він може виконувати наступну дію будь-яку кількість разів:

  1. вибрати будь-яку частину ,

  2. вибрати додатне ціле число (0 < x < 2^{30}), і за вартість монет змінити висоту частини a_j := a_j \mid x (пояснення символу доступне внизу сторінки).

У містера IP не так багато монет, тому тепер він цікавиться, яка найменша кількість монет йому потрібна, щоб знову зробити свій конструктор схожим на гору. Допоможіть йому знайти цю кількість!

Вхідні дані

Перший рядок вхідних даних містить ціле число (1 \le t \le 5 \cdot 10^4) — кількість тестових випадків. Кожен тестовий випадок потрібно вирішувати незалежно.

Перший рядок кожного тестового випадку містить ціле число (3 \le n \le 2 \cdot 10^5) — кількість частин у конструкторі.

Другий рядок кожного тестового випадку містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i < 2^{30}) — висоти частин.

Гарантується, що сума значень по всіх тестових випадках не перевищує 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — найменша кількість монет, необхідна для того, щоб конструктор містера IP виглядав як гора.

Приклади

Приклад 1

Loading
Loading

Примітка

Символ означає оператор "побітового OR".

Побітовий OR двох чисел та працює наступним чином:

  • Розглянемо двійкове представлення p = \overline{(p_0 p_1 \dots p_{29})}_2 та q = \overline{(q_0 q_1 \dots q_{29})}_2, де p_i, q_i \in \{0, 1\}, а p = \sum_{i=0}^{29} p_i \cdot 2^i та q = \sum_{i=0}^{29} q_i \cdot 2^i відповідно. Можна показати, що такі представлення є унікальними для кожного числа.

  • Результат операції r = \overline{(r_0 r_1 \dots r_{29})}_2 = \sum_{i=0}^{29} r_i \cdot 2^{i} обчислюється наступним чином:

  • r_i = p_i\ \textbf{or}\ q_i, де визначається наступним чином:

Перший біт

Другий біт

Біт результату

Наприклад,

  • якщо p = 5 = \overline{(1010)}_2 та q = 12 = \overline{(0011)}_2, тоді p \mid q = \overline{(1011)}_2 = 13;

  • якщо p = 6 = \overline{(011)}_2 та q = 7 = \overline{(111)}_2, тоді p \mid q = \overline{(111)}_2 = 7.

У першому наборі вхідних даних містер IP може виконати операцію двічі:

  1. вибрати частину , і за монети, зробити a_3 := 3 \mid 4 = 7.

  2. вибрати частину , і за монету, зробити a_5 := 2 \mid 1 = 3.

Після цього конструктор виглядає наступним чином: [2, 5, 7, 8, 3, 3] з індексом m = 4, що задовольняє умові a_1 \le a_2 \le a_3 \le a_4 \ge a_5 \ge a_6. Загальна вартість становить 4+1 = 5. Можна показати, що досягти мети з меншою вартістю неможливо.

У другому наборі вхідних даних містер IP може виконати операцію один раз на частині , заплативши монети, щоб зробити a_2 := 1 \mid 2 = 3. Жодна операція вартістю не може зробити конструктор схожим на гору; отже, це найменша відповідь.

У третьому випадку частина з індексом m = 5 вже задовольняє властивість a_1 \le a_2 \le a_3 \le a_4 \le a_5, отже, виконувати жодних операцій не потрібно.

Оцінювання

  1. ( балів): n \le 5, a_i \le 15

  2. ( балів): a_i \le 2

  3. ( балів): a_i \le 63

  4. ( балів): n \le 100

  5. ( балів): без додаткових обмежень.