#include #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std::literals::string_literals; using i64 = std::int_fast64_t; using std::cout; using std::cerr; using std::endl; using std::cin; template std::vector make_v(size_t a){return std::vector(a);} template auto make_v(size_t a,Ts... ts){ return std::vector(ts...))>(a,make_v(ts...)); } #define NDEBUG int main() { int n; scanf("%d", &n); std::vector s(n); for(int i = 0; i < n; i++) cin >> s[i]; std::vector a(n - 1); for(int i = 0; i < n - 1; i++) { for(int j = 0; j < std::min(s[i + 1].size(), s[i].size()); j++) { if(s[i][j] != s[i + 1][j]) break; a[i] = j + 1; } } i64 ans = 0; for(auto v: s) ans += v.size(); std::vector nxt(a.size()); for(int i = (int)a.size() - 1; i >= 0; i--) { int now = i + 1; while(now < a.size()) { if(a[now] < a[i]) break; now = nxt[now]; } nxt[i] = now; } #ifndef NDEBUG for(auto v: a) cout << v << " "; cout << endl; for(auto v: nxt) cout << v << " "; cout << endl; #endif for(int i = 0; i < a.size(); i++) { int now = i; while(now < a.size()) { i64 S = now - i + 2, T = nxt[now] - i + 1; i64 len = (S + T) * (T - S + 1) >> 1; ans += len * a[now]; now = nxt[now]; } } printf("%lld\n", ans); return 0; }