#include <bits/stdc++.h>
using namespace std;
vector<int> Prefix_MEX(vector<int>& A, int n)
{
int mx_element = *max_element(A.begin(), A.end());
set<int> s;
vector<int> B(n);
for (int i = 0; i <= mx_element + 1; i++) {
s.insert(i);
}
for (int i = 0; i < n; i++) {
auto it = s.find(A[i]);
if (it != s.end())
s.erase(it);
B[i] = *s.begin();
}
return B;
}
void countPairs(vector<int>& arr, int N)
{
int count = 0;
vector<int> P = Prefix_MEX(arr, N);
reverse(arr.begin(), arr.end());
vector<int> S = Prefix_MEX(arr, N);
reverse(S.begin(), S.end());
map<int, int> mp;
for (int i = 0; i < N; i++) {
mp[P[i]]++;
}
for (int i = 0; i < N; i++) {
if (mp.find(S[i]) == mp.end()) {
continue;
}
else {
count += mp[S[i]];
}
}
cout << count << endl;
}
int main()
{
vector<int> arr = { 1, 0, 2, 0, 1 };
int N = arr.size();
countPairs(arr, N);
arr = { 1, 2, 3 };
N = arr.size();
countPairs(arr, N);
return 0;
}