// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <numeric> #include <stack> #include <chrono> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> void fast_io(){ // freopen("", "r", stdin); // freopen("", "w", stdout); ios::sync_with_stdio(0); cin.tie(); cout.tie(); cout << setprecision(9); } #define int long long #define endl '\n' #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define fi first #define se second const int N = 2e5 + 5; int n, rep, a[N]; vector<int> idx[N]; int calculate(int I){ int ans = 0, m = idx[I].size(); vector<int> a = {}; if (idx[I][0] != 1) a.push_back(1 - idx[I][0]); a.push_back(1); for (int i = 1; i < m; i++){ if (idx[I][i - 1] - idx[I][i] + 1 != 0) a.push_back(idx[I][i - 1] - idx[I][i] + 1); a.push_back(1); } if (idx[I].back() != n) a.push_back(idx[I].back() - n); m = a.size(); int s = 0; ordered_set S; S.insert(0); for (int i = 0; i < m; i++){ s += a[i]; ans += S.order_of_key(s); S.insert(s); } return ans; } void solve() { cin >> n; map<int, int> c; for (int i = 1; i <= n; i++){ cin >> a[i]; if (c[a[i]]) a[i] = c[a[i]]; else { c[a[i]] = ++rep; a[i] = rep; } idx[a[i]].push_back(i); } int ans = 0; for (int i = 1; i <= n; i++){ // cout << calculate(i) << endl; if (idx[i].size() == 0) continue; ans += calculate(i); } cout << ans << endl; return; } signed main() { fast_io(); srand(chrono::steady_clock::now().time_since_epoch().count()); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }