// O(S^1.5) // includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); int n; cin >> n; string t; cin >> t; const int S = 2e5; assert(1 <= t.size() && t.size() <= S); for(auto c : t) assert('a' <= c && c <= 'z'); vector> cnt(S + 1); ll ans = t.size(); assert(ans <= S); for(int i = 1; i < n; i++) { string s; cin >> s; for(auto c : s) assert('a' <= c && c <= 'z'); assert(1 <= s.size() && s.size() <= S); int f = 0; while(f < s.size() && f < t.size() && s[f] == t[f]) f++; t = s; cnt.at(f).push_back(i); ans += s.size(); assert(ans <= S); } vector used(n+1); used[0] = used[n] = 1; for(int i = 0; i <= S; i++) if(cnt[i].size()) { int now = 0; int last = 0, last2; int lasti = -1; ll x, x2; for(int k = 1; k <= n; k++) { if(now < cnt[i].size() && cnt[i].at(now) == k) { used[k] = 1; x2 = k - last; last2 = last; } if(lasti >= 0 && used[k]) { ll y = k - lasti; ans += ((x * x * y + x * y * y) / 2 + x * y) * i; lasti = -1; } if(used[k]) last = k; if(now < cnt[i].size() && cnt[i].at(now) == k) { now++; x = x2; last = last2; lasti = k; } } } cout << ans << endl; return 0; }