vi buildLCP(vi &sa, vi &s, ll &ans, int sz)
{
    int n = s.size();
    vi lcp(n);
    vi pos(n);
    int l = 0;
    for (int i = 0; i < n; ++i)
    {
        pos[sa[i]] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        if (pos[i] == n - 1)
        {
            l = 0;
            continue;
        }
        l = max(l - 1, 0);
        int j = sa[pos[i] + 1];
        while (l < n && s[(i + l) % n] == s[(j + l) % n])
            ++l;
        lcp[pos[i]] = l;
    }
    for (int i = 0; i < sz; ++i)
        ans += lcp[pos[i]];
    return lcp;
}

int solve(int n)
{
    vi a(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; ++i)
    {
        a.inb(a[i]);
    }
    vi sa = buildSuffArray(a);
    ll ans = 0;
    vi lcp = buildLCP(sa, a, ans, n);
    printf("%lld\n", ans);
    return 0;
}