Source Code
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(s)    (int)(s.size())
const ll N = 2e5+3, mod = 1000000007;
const ll OO = 6e18;
const auto EPS = 1e-6;
const auto PI = acos(-1);
using namespace std;
int DX[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int DY[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dx[] = { 1,0,-1,0 } ,dy[] = { 0,1,0,-1 };

void testCase()
{
	int n;
	cin >> n;
	vector<ll>a(n);
	ll idx = -1;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		if(a[i] == 0)
			idx = i;
	}
	ll sum = 0;
	ll mex = 1;
	vector<bool>vis(n);
	//vis[0] = 1;
	for(int i=idx+1;i<n;i++)
	{
		vis[a[i]] = 1;
		while(vis[mex])mex++;
		sum += mex;
	}
	ll right = 0;
	if(sum)right = sum - mex;
	mex = 1;
	vis = vector<bool>(n);
	for(int i=idx-1;i>=0;i--)
	{
		vis[a[i]] = 1;
		while(vis[mex])mex++;
		sum += mex;
	}
	mex = 1;
	vis = vector<bool>(n);
	for(int i=idx+1;i<n;i++)
	{
		vis[a[i]] = 1;
		while(vis[mex])mex++;
	}
	if(!right)
	{
		cout << sum+1 << '\n';
		return; 
	}
	for(int i=idx-1;i>=0;i--)
	{
		vis[a[i]] = 1;
		while(vis[mex])mex++;
		sum += mex;
		sum += right;
	}
	cout << sum+1 << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;   cin >> t;
    for(int tc = 1;tc<=t;tc++)
    {
        //cout << "Case #" << tc << ": ";
        testCase();
    }
    return 0;
}
Copy
Mex MuhammedKhedr
GNU G++17
17 ms
304 KB
Wrong Answer