In this HackerEarth Mathison and the exceptional list problem solution Mathison has practiced different operations that can be performed on lists. Unfortunately, he has found a set of operations that he cannot perform efficiently so he asks for your help.

You start with an empty list, on which you perform N operations. In one operation (e, L, R) you add e to the back of the list and print the number of exceptional subarrays with the length between L and R inclusive, in the current version of the list. An exceptional subarray is defined to be a subarray of the list that contains only unique elements (i.e. no two elements share the same value).

## HackerEarth Mathison and the exceptional list problem solution.

```#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <cassert>

using namespace std;

constexpr int MAX_N = 500'000 + 2;
array<long long, MAX_N> fenwick1, fenwick2;

inline constexpr int lsb(int x){
return x & -x;
}

void update(array<long long, MAX_N> &fenwick, int pos, long long value){
while (pos < MAX_N){
fenwick[pos] += value;
pos += lsb(pos);
}
}

void update_range(int a, int b, long long value){
update(fenwick1, a, value);
update(fenwick1, b + 1, -value);
update(fenwick2, a, value * (a - 1));
update(fenwick2, b + 1, -value * b);
}

long long query(const array<long long, MAX_N> &fenwick, int pos){
long long sum = 0;

while (pos > 0){
sum += fenwick[pos];
pos -= lsb(pos);
}

return sum;
}

long long query(int b){
return 1LL * query(fenwick1, b) * b - query(fenwick2, b);
}

long long query_range(int a, int b){
if (a > b)
return 0;
else
return query(b) - query(a - 1);
}

int main(){
ios_base::sync_with_stdio(false);

int N;
cin >> N;
assert(1 <= N && N <= 500'000);

unordered_map<int, int> umap;
umap.reserve(4096);

int last_pos = -1;

for (int i = 0; i < N; i++){
int e;
cin >> e;
assert(0 <= e && e <= 1'000'000'000);

int L, R;
cin >> L >> R;
assert(1 <= L && L <= N);
assert(1 <= R && R <= N);

auto it = umap.find(e);

if (it != umap.end())
last_pos = max(last_pos, it->second);

umap[e] = i;
int lg = i - last_pos;

update_range(1, lg, +1);

auto s = query_range(L, R);
assert(s >= 0);
cout << s << "\n";
}

return 0;
}```

### Second solution

```#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;
long long lazy[4 * MAXN];
long long seg[4 * MAXN];
pair<int, int> temp[MAXN];
int e[MAXN], l[MAXN], r[MAXN];
int MX[MAXN];
int dp[MAXN];

void update(int node, int start, int end, int qs, int qe) {
if(lazy[node]) {
seg[node] += 1LL * lazy[node] * (end - start + 1);
if(start != end) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
if(start > end or qe < start or qs > end) return;
if(start >= qs and end <= qe) {
seg[node] += 1LL * (end - start + 1);
if(start != end) {
lazy[2 * node]++;
lazy[2 * node + 1]++;
}
return;
}
int mid = (start + end) >> 1;
update(2 * node, start, mid, qs, qe);
update(2 * node + 1, mid + 1, end, qs, qe);
seg[node] = seg[2 * node] + seg[2 * node + 1];
}

long long query(int node, int start, int end, int qs, int qe) {
if(lazy[node]) {
seg[node] += 1LL * lazy[node] * (end - start + 1);
if(start != end) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
if(start > end or qe < start or qs > end) return 0;
if(start >= qs and end <= qe) {
return seg[node];
}
int mid = (start + end) >> 1;
long long ret = query(2 * node, start, mid, qs, qe) + query(2 * node + 1, mid + 1, end, qs, qe);
seg[node] = seg[2 * node] + seg[2 * node + 1];
return ret;
}
int main() {
int q;
scanf("%d", &q);
assert(q <= 500000 and q >= 1);
for(int i = 1; i <= q; i++) {
scanf("%d%d%d", &e[i], &l[i], &r[i]);
assert(e[i] >= 1 and e[i] <= 1000000000);
assert(l[i] >= 1 and l[i] <= q);
assert(r[i] >= 1 and r[i] <= q);
temp[i].first = e[i];
temp[i].second = i;
}
sort(temp + 1, temp + 1 + q);
int cur = 1;
e[temp[1].second] = cur;
for(int i = 2; i <= q; i++) {
if(temp[i].first != temp[i - 1].first) ++cur;
e[temp[i].second] = cur;
}
for(int i = 1; i <= q; i++) {
int mx = MX[e[i]];
mx = max(mx, dp[i - 1]);
MX[e[i]] = i;
dp[i] = mx;
update(1, 1, q, 1, i - mx);
printf("%lld\n", query(1, 1, q, l[i], r[i]));
}
return 0;
}```