use std::io::Read; fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let s: Vec> = (0..n) .map(|_| itr.next().unwrap().chars().collect()) .collect(); let mut ans: u64 = 0; let mut stack: Vec<(u64, u64)> = Vec::new(); for i in 0..n { ans += s[i].len() as u64; if i == n - 1 { while let Some((cnt, pos)) = stack.pop() { let l = i as u64 - pos + 1; if let Some((c, p)) = stack.pop() { ans += (cnt - c) * (l * (l + 1) * (l + 2) / 6 - l); stack.push((c, p)); } else { ans += cnt * (l * (l + 1) * (l + 2) / 6 - l); } } break; } let mut m: u64 = 0; let k = std::cmp::min(s[i].len(), s[i + 1].len()); for j in 0..k { if s[i][j] != s[i + 1][j] { break; } m += 1; } // 今よりマッチ数が小さくなるまでpop let mut next: u64 = i as u64; while let Some((cnt, pos)) = stack.pop() { if cnt == m { next = pos; break; } else if cnt < m { stack.push((cnt, pos)); break; } let l = i as u64 - pos + 1; if let Some((c, p)) = stack.pop() { ans += (cnt - std::cmp::max(m, c)) * (l * (l + 1) * (l + 2) / 6 - l); // 自分と同じ一番前を取得 stack.push((c, p)); } else { ans += (cnt - m) * (l * (l + 1) * (l + 2) / 6 - l); } next = pos; } stack.push((m, next)); } println!("{}", ans); }