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 mut a: u64 = i as u64 - pos + 1; let mut b: u64 = 1; while a > 1 { ans += cnt * a * b; a -= 1; b += 1; } } 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; } if m > 0 { // 今よりマッチ数が小さくなるまでpop let mut need: bool = true; while let Some((cnt, pos)) = stack.pop() { if cnt == m { need = false; stack.push((cnt, pos)); break; } else if cnt < m { stack.push((cnt, pos)); break; } let mut a: u64 = i as u64 - pos + 1; let mut b: u64 = 1; while a > 1 { ans += (cnt - m) * a * b; a -= 1; b += 1; } } if need { stack.push((m, i as u64)); } } } println!("{}", ans); }