#include <iostream>
#include <vector>
#include <string>
#include <random>

using namespace std;

using ll = long long;
using ld = long double;

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())

mt19937 rnd(234);
const int inf = 1e8;

struct SGT {
    int n;
    vector<pair<int, int>> t;

    void build(vector<int> a) {
        n = 1;
        while (n < len(a)) {
            n *= 2;
        }
        t.resize(2 * n);
        rep(i, len(a)) {
            t[i + n] = {a[i], i};
        }
        for (int i = n - 1; i >= 0; i -= 1) {
            t[i] = min(t[i + i], t[i + i + 1]);
        }
    }

    pair<int, int> get(int l, int r) {
        l += n;
        r += n + 1;
        pair<int, int> rs = {inf + 1, -1};
        while (l < r) {
            if (l & 1) {
                rs = min(rs, t[l]);
                ++l;
            }
            if (r & 1) {
                --r;
                rs = min(rs, t[r]);
            }
            l /= 2;
            r /= 2;
        }
        return rs;
    }
};

const int C = 2;

int bases[C] = {179, 57};
int moduls[C] = {(int)1e9 + 7, 1791791791};

inline int add(int a, int b, int mod) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

inline int sub(int a, int b, int mod) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}

inline int mul(int a, int b, int mod) {
    return 1ll * a * b % mod;
}

struct Hasher {
    int flex[C];

    Hasher() {
        for (int i = 0; i < C; ++i) flex[i] = 0;
    }

    Hasher(int x) {
        for (int i = 0; i < C; ++i) {
            flex[i] = x % moduls[i];
        }
    }
};

Hasher operator+(const Hasher& a, const Hasher& b) {
    Hasher ans;
    for (int i = 0; i < C; ++i) {
        ans.flex[i] = add(a.flex[i], b.flex[i], moduls[i]);
    }
    return ans;
}

bool operator ==(const Hasher& a, const Hasher& b) {
    for (int i = 0; i < C; ++i) {
        if (a.flex[i] != b.flex[i]) {
            return false;
        }
    }
    return true;
}

int n;
vector<string> a;
vector <vector <Hasher>> hashs;
vector<int> d;
const int MAXN = 3e6;
int powers[C][MAXN];
int pref[C][MAXN];
SGT sgt;

bool cmp(const string &a, const string &b) {
    rep(i, max(len(a), len(b)) * 2) {
        if (a[i % len(a)] != b[i % len(b)]) {
            return (a[i % len(a)] < b[i % len(b)]);
        }
    }
    return false;
}

Hasher get_hash(int ind, int len) {
    int aln = a[ind].size();
    int cnt_ful = len / aln;

    Hasher cur_hash;
    if (cnt_ful > 0) {
        cur_hash = hashs[ind].back();
        for (int i = 0; i < C; ++i) {
            int coef = pref[i][cnt_ful - 1];
            coef = mul(coef, powers[i][len - cnt_ful * aln], moduls[i]);
            cur_hash.flex[i] = mul(cur_hash.flex[i], coef, moduls[i]);
        }
    }

    cur_hash = cur_hash + hashs[ind][len % aln];
    return cur_hash;
}

bool lesha_cmp(int i, int j) {
    int max_len = max(len(a[i]), len(a[j])) * 2;

    if (get_hash(i, max_len) == get_hash(j, max_len)) {
        return false;
    }

    int l = 0;
    int r = max_len;

    while (r - l > 1) {
        int m = (l + r) / 2;
        if (get_hash(i, m) == get_hash(j, m)) l = m;
        else r = m;
    }
    //r - len
    //l - index
    return a[i][l % len(a[i])] < a[j][l % len(a[j])];
}

void build_hash() {
    hashs.assign(n, {});
    for (int i = 0; i < n; ++i) {
        hashs[i].resize(a[i].size() + 1);
        for (int j = 0; j < a[i].size(); ++j) {
            hashs[i][j + 1] = hashs[i][j];
            for (int k = 0; k < C; ++k) {
                hashs[i][j + 1].flex[k] = mul(hashs[i][j + 1].flex[k], bases[k], moduls[k]);
            }
            hashs[i][j + 1] = hashs[i][j + 1] + Hasher(a[i][j] - 'A');
        }
    }

    for (int i = 0; i < C; ++i) {
        powers[i][0] = 1;
        pref[i][0] = 1;
        for (int j = 1; j < MAXN; ++j) {
            powers[i][j] = mul(powers[i][j - 1], bases[i], moduls[i]);
            pref[i][j] = add(pref[i][j - 1], powers[i][j], moduls[i]);
        }
    }
}

ll solve(ll l, ll r) {
    if (r - l + 1 < 3) {
        return 0;
    }
    auto [mn, pos] = sgt.get(l, r - 1);
    if (mn == inf) {
        return 0;
    }
    if (r == pos + 1) {
        return solve(l, pos);
    }
    auto [mn2, pos2] = sgt.get(pos + 1, r - 1);
    if (mn != mn2) {
        ll res1 = solve(l, pos);
        ll res2 = solve(pos + 1, r);
        return res1 + res2;
    }
    ll myres = ll(pos - l + 1) * (pos2 - pos) * (r - pos2);
    ll res1 = solve(l, pos);
    ll res2 = solve(pos + 1, pos2);
    ll res3 = solve(pos2 + 1, r);
    return myres + res1 + res2 + res3;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    a.resize(n);
    rep(i, n) {
        cin >> a[i];
    }
    build_hash();
//    sort(all(a), cmp);
    if (1) {
        vector <string> flex = a;
        sort(all(flex), cmp);
        for (auto i : flex) cout << i << "\n";
        cout << "------\n";
    }

    //my_sort
    vector <int> indices(n);
    for (int i = 0; i < n; ++i) indices[i] = i;

    sort(all(indices), lesha_cmp);

    vector <string> na(n);
    for (int i = 0; i < n; ++i) {
        na[i] = a[indices[i]];
    }
    a = na;
    if (1) {
        for (auto i : a) {
            cout << i << "\n";
        }
    }
    d.resize(n - 1);
    rep(i, n - 1) {
        d[i] = inf;
        for (int j = 0; j < max(len(a[i]), len(a[i + 1])) * 2; j += 1) {
            if (a[i][j % len(a[i])] != a[i + 1][j % len(a[i + 1])]) {
                d[i] = j;
                break;
            }
        }
    }
    sgt.build(d);
    ll result = solve(0, n - 1);
    cout << result << "\n";
    return 0;
}

answer.code: In function ‘int32_t main()’:
answer.code:227:9: error: ‘sort’ was not declared in this scope; did you mean ‘sqrt’?
  227 |         sort(all(flex), cmp);
      |         ^~~~
      |         sqrt
answer.code:236:5: error: ‘sort’ was not declared in this scope; did you mean ‘sqrt’?
  236 |     sort(all(indices), lesha_cmp);
      |     ^~~~
      |     sqrt