TEAMBOOK суффиксный массив

#include <bits/stdc++.h>
using long_type = long long;
#define long long_type
using namespace std;

const int max_n     = 3e5;
const int alphabet  = 101;
int n, arr[max_n], suf[max_n], eq[max_n], temp[max_n], inv[max_n], lcp[max_n];
vector<int> bucket[max_n];

int mod(int i) {
    i += n;
    return i % n;
}

void check(int i, int j) {
    for (int k = 0; ; ++k) {
        if (arr[i + k] != arr[j + k]) {
            assert(arr[i + k] < arr[j + k]);
            return;
        }
    }
}

void solve() {
    assert(n <= 50000);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        ++arr[i];
        arr[i + n] = arr[i];
    }
    arr[2 * n] = 0;
    n = 2 * n + 1;
    for (int i = 0; i < n; ++i) {
        eq[i] = arr[i];
    }
    iota(suf, suf + n, 0);
    sort(suf, suf + n, [&](int i, int j) {
        return arr[i] < arr[j];
    });
    for (int len = 1; len < n; len *= 2) {
        for (int i = 0; i < n; ++i) {
            int j = mod(suf[i] - len);
            bucket[eq[j]].push_back(j);
        }
        int ptr = 0;
        for (int num = 0; num < n || num <= alphabet; ++num) {
            for (int i : bucket[num]) {
                suf[ptr++] = i;
            }
            bucket[num].clear();
        }
        temp[suf[0]] = 0;
        for (int i = 1; i < n; ++i) {
            temp[suf[i]] = temp[suf[i - 1]];
            int a = eq[suf[i - 1]], b = eq[mod(suf[i - 1] + len)];
            int c = eq[suf[i]],     d = eq[mod(suf[i] + len)];
            if (a != c || b != d) {
                ++temp[suf[i]];
            }
        }
        copy(temp, temp + n, eq);
    }
    for (int i = 0; i < n; ++i) {
        //~ cout << suf[i] << " ";
        inv[suf[i]] = i;
    }
    //~ cout << endl;
    int k = 0;
    long answer = 0;
    for (int i = 0; i < n; ++i) {
        if (inv[i] == n - 1) {
            k = 0;
            continue;
        }
        k = max(0, k - 1);
        int j = suf[inv[i] + 1];
        while (k < n && arr[i + k] == arr[j + k]) {
            ++k;
        }
        lcp[i] = k;
    }
    int cur = n;
    bool was = false;
    for (int i = 0; i < n; ++i) {
        if (suf[i] < n / 2) {
            if (was) {
                answer += min(cur, n / 2);
                //cout << min(cur, n / 2) << " ";
            }
            cur = lcp[suf[i]];
            was = true;
        } else {
            cur = min(cur, lcp[suf[i]]);
        }
    }
    cout << answer << "\n";
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
    assert(freopen("towers.in", "r", stdin));
    assert(freopen("towers.out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n && n) {
        solve();
    }
    return 0;
}