Вам дан массив $$$a$$$ длины $$$n$$$. Назовем целое положительное число $$$x$$$ хорошим, если нельзя найти такой подотрезок$$$^{\dagger}$$$ массива, что наименьшее общее кратное всех элементов на нём равно $$$x$$$.
Вам требуется найти наименьшее хорошее число.
Подотрезком $$$^{\dagger}$$$ массива $$$a$$$ называется набор элементов $$$a_l, a_{l + 1}, \ldots, a_r$$$ для некоторых $$$1 \le l \le r \le n$$$. Будем обозначать такой подотрезок $$$[l, r]$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных выведите единственное целое число — наименьшее хорошее число.
631 2 351 2 3 4 522 311000000000121 8 4 2 3 5 7 2 9 10 11 13127 2 5 4 2 1 1 2 3 11 8 9
4 7 1 1 16 13
В первом наборе входных данных, $$$4$$$ — хорошее число, при этом оно является наименьшим, так как числа $$$1,2,3$$$ встречаются в массиве, а значит, есть подотрезки массива длины $$$1$$$ с наименьшими общими кратными $$$1,2,3$$$. При этом нельзя найти подотрезок массива с наименьшим общим кратным равным $$$4$$$.
Во втором наборе входных данных, $$$7$$$ — хорошее число. При этом числа $$$1,2,3,4,5$$$ встречаются в массиве явно, а число $$$6$$$ является наименьшим общим кратных подотрезков $$$[2, 3]$$$ и $$$[1, 3]$$$.
В третьем наборе входных данных, $$$1$$$ — хорошее число, так как наименьшие общие кратные для чисел на отрезках $$$[1, 1], [1, 2], [2, 2]$$$, соответственно, равны $$$2,6,3$$$.
| Codeforces Round 879 (Div. 2) |
|---|
| Закончено |
