#include <bits/stdc++.h>   using namespace std;   struct SuffixArray {     char* T;     int n;     vector<int> RA, tempRA;     vector<int> SA, tempSA, c;     vector<int> phi, pLCP, LCP;     SuffixArray(string& t) {       n = t.length();       T = new char[n + n];       for (int i = 0; i < n; T[i] = t[i], i++)         ;       T[n++] =  # , T[n] =   0 ;       c.resize(max(300, n));       RA.resize(n), tempRA.resize(n);       SA.resize(n), tempSA.resize(n);     }     void countingSort(int k) {       fill(c.begin(), c.end(), 0);       for (int i = 0; i < n; i++) c[i + k < n ? RA[i + k] : 0]++;       for (int i = 0, sum = 0, lim = max(300, n); i < lim; i++) {         int t = c[i];         c[i] = sum, sum += t;       }       for (int i = 0; i < n; i++)         tempSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];       for (int i = 0; i < n; i++) SA[i] = tempSA[i];     }     void buildSA() {       for (int i = 0; i < n; SA[i] = i, i++)         ;       for (int i = 0; i < n; RA[i] = T[i], i++)         ;       for (int k = 1, r; k < n; k <<= 1) {         countingSort(k);         countingSort(0);         tempRA[SA[0]] = r = 0;         for (int i = 1; i < n; i++) {           tempRA[SA[i]] =               (RA[SA[i]] == RA[SA[i - 1]] and RA[SA[i] + k] == RA[SA[i - 1] + k]                    ? r                    : ++r);         }         for (int i = 0; i < n; RA[i] = tempRA[i], i++)           ;         if (RA[SA[n - 1]] == n - 1) break;       }     }     void computeLCP() {       phi.resize(n), pLCP.resize(n), LCP.resize(n);       phi[SA[0]] = -1;       for (int i = 1; i < n; phi[SA[i]] = SA[i - 1], i++)         ;       for (int i = 0, L = 0; i < n; i++) {         if (phi[i] == -1) {           pLCP[i] = 0;           continue;         }         for (; T[i + L] == T[phi[i] + L]; L++)           ;         pLCP[i] = L;         L = max(0, L - 1);       }       for (int i = 0; i < n; LCP[i] = pLCP[SA[i]], i++)         ;     }     void print() {       for (int i = 0; i + 1 < n; i++) {         printf( %2d t%2d t%s n , SA[i], LCP[i], T + SA[i]);       }     }   };   struct Node {     int sum, lft, rgt;     Node() : sum(0), lft(0), rgt(0) {}   };   struct PersistantSegmentTree {     int avail;     vector<int> roots;     vector<Node> tree;     PersistantSegmentTree(int n) {       avail = 0;       roots.resize(n + 10, 0);       tree.resize(n * 30, Node());     }     int update(int last, int l, int r, int p) {       int cur = ++avail;       tree[cur] = tree[last];       if (l == r) {         tree[cur].sum++;         return cur;       }       int mid = l + (r - l) / 2;       if (p <= mid)         tree[cur].lft = update(tree[last].lft, l, mid, p);       else         tree[cur].rgt = update(tree[last].rgt, mid + 1, r, p);       tree[cur].sum = tree[tree[cur].lft].sum + tree[tree[cur].rgt].sum;       return cur;     }     int query(int cur, int l, int r, int L, int R) {       if (l > R or r < L or L > R) return 0;       if (l >= L and r <= R) return tree[cur].sum;       int mid = l + (r - l) / 2;       int pp = query(tree[cur].lft, l, mid, L, R);       int qq = query(tree[cur].rgt, mid + 1, r, L, R);       return pp + qq;     }   };   int main() {     ios_base ::sync_with_stdio(0);     cin.tie(0), cout.tie(0);     int n;     string s;     cin >> n >> s;     SuffixArray SA(s);     SA.buildSA();     SA.computeLCP();     PersistantSegmentTree PSG(SA.n);     vector<int> have;     for (int i = n - 1; i >= 0; i--) {       if (s[i] ==  ) ) {         have.push_back(i);         continue;       }       if (!have.empty()) {         PSG.roots[i] =             PSG.update(PSG.roots[have.back() + 1], 0, SA.n, have.back());         have.pop_back();       }     }     long long res = 0;     for (int i = 1; i < SA.n; i++) {       if (s[SA.SA[i]] ==  ) ) continue;       int L = SA.SA[i];       int R = L + SA.LCP[i] - 1;       int add = PSG.query(PSG.roots[L], 0, SA.n, L, SA.n);       int bad = PSG.query(PSG.roots[L], 0, SA.n, L, R);       res += (0, max(0, add - bad));     }     cout << res <<   n ;   }   