Given a sequence (a) of (n) positive integers, a positive integer (x) is considered non-humor if there exists a contiguous subarray whose least common multiple (LCM) equals (x). The task is to find the smallest positive integer that is not non-humor, i.e., the minimum excluded value (MEX) from the set of all subarray LCMs.

Input/Output Format

Input begins with an integer (T) (number of test cases). For each case, the first line contains (n), followed by (n) integers (a_1, a_2, \dots, a_n). For each test case, output the smallest positive integer not present as the LCM of any subarray.

Constraints

• (1 \leq T \leq 10)
• (1 \leq n \leq 10^5)
• (1 \leq a_i \leq 10^9)

Key Insight

Observing the behvaior of LCM when extending a subarray reveals a critical property: for a fixed starting index (i), the set of LCMs of subarrays ([i, j]) for (j \geq i) grows slowly. Specifically, as we move the right endpoint (j) from (i) to (n), the LCM can only change when a new element introduces a prime factor not already present in the current LCM. Consequently, for each starting index, the number of distinct LCM values generated is bounded by (O(\log \max_value)).

Therefore, we can efficiently compute all possible subarray LCMs by iterating through each starting index and maintaining the set of LCMs ending at the current position. Duplicate LCMs across different starts are managed using a global set.

Algorithm

1. Initialize a global set total_lcms to store all distinct LCMs found.
2. For each index i from 0 to n-1:
   • Create a new set current_lcms containing the element a[i].
   • For each LCM value prev_lcm from the set of LCMs ending at the previous index (prev_set), compute new_lcm = lcm(prev_lcm, a[i]).
   • If new_lcm does not exceed a practical upper bound (to prevent overflow and manage comlpexity), add it to current_lcms.
   • Update prev_set to be current_lcms for the next iteration.
   • Insert all values from current_lcms into the global total_lcms.
3. After processing the sequence, find the smallest positive integer k not present in total_lcms. This is the answer.

Complexity: (O(n \cdot L \cdot \log M)), where (L) is the bound on distinct LCMs per start (practically small, e.g., (\sim 60) for constraints), and (M) is the maximum LCM value considered.

Implementation Example

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

const ll LCM_LIMIT = 2'000'000'000LL; // Practical upper bound

ll compute_lcm(ll x, ll y) {
    return x / __gcd(x, y) * y;
}

ll find_mex_of_lcms(const vector<int>& arr) {
    set<ll> all_lcms;
    set<ll> previous_lcms;

    for (int val : arr) {
        set<ll> current_lcms;
        current_lcms.insert(val);

        for (ll l : previous_lcms) {
            ll new_lcm = compute_lcm(l, val);
            if (new_lcm <= LCM_LIMIT) {
                current_lcms.insert(new_lcm);
            }
        }
        previous_lcms = current_lcms;
        all_lcms.insert(current_lcms.begin(), current_lcms.end());
    }

    ll candidate = 1;
    while (all_lcms.count(candidate)) {
        ++candidate;
    }
    return candidate;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n;
        cin >> n;
        vector<int> sequence(n);
        for (int i = 0; i < n; ++i) {
            cin >> sequence[i];
        }
        cout << find_mex_of_lcms(sequence) << '\n';
    }
    return 0;
}

Sample Execution

Input:

6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9

Output:

4
7
1
1
16
13

Explanation of First Case

For the sequence [1, 2, 3], the subarray LCMs are:

• [1] -> 1
• [2] -> 2
• [3] -> 3
• [1,2] -> 2
• [2,3] -> 6
• [1,2,3] -> 6 The set of LCMs is {1, 2, 3, 6}. The smallest positive integer not in this set is 4.