1834E - MEX of LCM - CodeForces Solution

#include <bits/stdc++.h>
#define mod 1000000007
#define init(arr, val) memset(arr, val, sizeof(arr))
#define fr(a,b) for(ll i = a; i < b; i++)
#define loop(i, a, b) for (ll i = a; i < b; i++)
#define loopr(i, a, b) for (ll i = a; i >= b; i--)
#define loops(i, a, b, step) for (ll i = a; i < b; i += step)
#define looprs(i, a, b, step) for (ll i = a; i >= b; i -= step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define pll pair<long long, long long>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define fast_io                       \
	ios_base::sync_with_stdio(false); \
	cin.tie();                        \
	cout.tie()
#define FILE_READ_IN freopen("input.txt", "r", stdin);
#define FILE_READ_OUT freopen("output.txt", "w", stdout);
#define prDouble(x) cout << fixed << setprecision(10) << x
#define all(a) a.begin(), a.end()
#define ld long double
#define inf (1LL<<60)
using namespace std;
const ll maxn = 2e5 + 1;
const double pi = acos(-1);


int main() {
	fast_io;
	int tests = 1;
	cin >> tests;
	ll limit = 1e9;
	for (int test_case = 1; test_case <= tests; test_case++) {
		int n; cin >> n;
		ll a[n];
		fr(0, n) cin >> a[i];
		set<ll> ending;
		set<ll> all_ending;
		fr(0, n) {
			set<ll> new_ending;
			new_ending.insert(a[i]);
			all_ending.insert(a[i]);
			for (auto j : ending) {
				if (lcm(j, a[i]) < limit) {
					new_ending.insert(lcm(j, a[i]));
					all_ending.insert(lcm(j, a[i]));
				}
			}
			swap(new_ending, ending);
		}
		ll i = 1;
		while (1) {
			if (all_ending.find(i) == all_ending.end()) {
				cout << i << endl;
				break;
			}
			i++;
		}
	}
	return 0;
}