#include <bits/stdc++.h> using namespace std; #define int long long struct segment_tree{ vector<int> seg, lazy; int N; void init(int n){ seg.resize(n * 4); lazy.resize(n * 4, 0); N = n; } void push(int node, int start, int end){ if(lazy[node] == 0) return; seg[node] += (end - start + 1) * lazy[node]; if(start ^ end){ lazy[node * 2 + 1] += lazy[node]; lazy[node * 2 + 2] += lazy[node]; } lazy[node] = 0; } void pull(int node){ seg[node] = seg[node * 2 + 1] + seg[node * 2 + 2]; } void update(int node, int start, int end, int l, int r, int x){ push(node, start, end); if(start > r || end < l) return; if(start >= l && end <= r){ lazy[node] = x; push(node, start, end); return; } int mid = start + (end - start) / 2; update(node * 2 + 1, start, mid, l, r, x); update(node * 2 + 2, mid + 1, end, l, r, x); pull(node); } void update(int node, int start, int end, int idx, int v){ push(node, start, end); if(start == end){ seg[node] = v; return; } int mid = start + (end - start) / 2; if(idx <= mid) update(node * 2 + 1, start, mid, idx, v); else update(node * 2 + 2, mid + 1, end, idx, v); pull(node); } int query(int node, int start, int end, int l, int r){ push(node, start, end); if(start > r || end < l) return 0; if(start >= l && end <= r) return seg[node]; int mid = start + (end - start) / 2; return query(node * 2 + 1, start, mid, l, r) + query(node * 2 + 2, mid + 1, end, l, r); } int query(int l, int r){ return query(0, 1, N, l, r); } void update(int idx, int v){ update(0, 1, N, idx, v); } void update(int l, int r, int v){ update(0, 1, N, l, r, v); } } tr; signed main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); int n, q; cin >> n >> q; vector<int> ar(n + 1, 0); for(int i = 1; i <= n; ++i) cin >> ar[i]; sort(ar.begin() + 1, ar.end()); assert(q == 1); tr.init(n); unordered_map<int, int> pos; while(q--){ int l, r; cin >> l >> r; int ans = 0; for(int i = 1; i <= n; ++i){ if(pos.count(ar[i])){ tr.update(pos[ar[i]] + 1, i, 1); }else{ tr.update(1, i, 1); } ans += tr.query(1, i); pos[ar[i]] = i; } cout << ans << "\n"; } return 0; }