E. MEX of LCM
binary search; data structures; implementation; math; number theory
You are given an array \(a\) of length \(n\). A positive integer \(x\) is called good if it is impossible to find a subsegment\(^{\dagger}\) of the array such that the least common multiple of all its elements is equal to \(x\).You need to find the smallest good integer.A subsegment\(^{\dagger}\) of the array \(a\) is a set of elements \(a_l, a_{l + 1}, \ldots, a_r\) for some \(1 \le l \le r \le n\). We will denote such subsegment as \([l, r]\).
Each test consists of multiple test cases. The first line of each test case contains a single integer \(t\) (\(1 \le t \le 5 \cdot 10^4\)) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \leq n \leq 3 \cdot 10^5\)) — the length of the array \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots , a_n\) (\(1 \leq a_i \leq 10^9\)) — the elements of the array \(a\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(3 \cdot 10^5\).
For each test case, output a single integer — the smallest good integer.
In the first test case, \(4\) is a good integer, and it is the smallest one, since the integers \(1,2,3\) appear in the array, which means that there are subsegments of the array of length \(1\) with least common multiples of \(1,2,3\). However, it is impossible to find a subsegment of the array with a least common multiple equal to \(4\).In the second test case, \(7\) is a good integer. The integers \(1,2,3,4,5\) appear explicitly in the array, and the integer \(6\) is the least common multiple of the subsegments \([2, 3]\) and \([1, 3]\).In the third test case, \(1\) is a good integer, since the least common multiples for the integer in the subsegments \([1, 1], [1, 2], [2, 2]\) are \(2,6,3\), respectively.