{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$. For each $1\\leq i\\leq N$, let $S_i$ denote the string obtained by deleting the $i$\\-th character from $S$.\nFind the number of pairs of integers $(i,j)$ that satisfy both of the conditions below.\n\n*   $1\\leq i < j\\leq N$\n*   $S_i = S_j$"},{"iden":"constraints","content":"*   $2\\leq N\\leq 3\\times 10^5$\n*   $S$ is a string of length $N$ consisting of lowercase English letters."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"7\nabbbcca"},{"iden":"sample output 1","content":"4\n\nHere are the strings $S_i$ in order: `bbbcca`, `abbcca`, `abbcca`, `abbcca`, `abbbca`, `abbbca`, `abbbcc`.\nThe following $4$ pairs $(i,j)$ satisfy the conditions.\n\n*   $(i,j) = (2,3)$\n*   $(i,j) = (2,4)$\n*   $(i,j) = (3,4)$\n*   $(i,j) = (5,6)$"},{"iden":"sample input 2","content":"4\nxxxx"},{"iden":"sample output 2","content":"6"},{"iden":"sample input 3","content":"2\npp"},{"iden":"sample output 3","content":"1"},{"iden":"sample input 4","content":"2\nst"},{"iden":"sample output 4","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}