Contest Duration: - (local time) (120 minutes) Back to Home
A - Remove One Character /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 1\leq i < j\leq N
• S_i = S_j

### 制約

• 2\leq N\leq 3\times 10^5
• S は英小文字からなる長さ N の文字列である

### 入力

N
S


### 入力例 1

7
abbbcca


### 出力例 1

4


S_i は、順に以下の文字列となります：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc

• (i,j) = (2,3)
• (i,j) = (2,4)
• (i,j) = (3,4)
• (i,j) = (5,6)

### 入力例 2

4
xxxx


### 出力例 2

6


### 入力例 3

2
pp


### 出力例 3

1


### 入力例 4

2
st


### 出力例 4

0


Score : 300 points

### Problem Statement

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.

Find the number of pairs of integers (i,j) that satisfy both of the conditions below.

• 1\leq i < j\leq N
• S_i = S_j

### Constraints

• 2\leq N\leq 3\times 10^5
• S is a string of length N consisting of lowercase English letters.

### Input

Input is given from Standard Input in the following format:

N
S


### Sample Input 1

7
abbbcca


### Sample Output 1

4


Here are the strings S_i in order: bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc.

The following 4 pairs (i,j) satisfy the conditions.

• (i,j) = (2,3)
• (i,j) = (2,4)
• (i,j) = (3,4)
• (i,j) = (5,6)

### Sample Input 2

4
xxxx


### Sample Output 2

6


### Sample Input 3

2
pp


### Sample Output 3

1


### Sample Input 4

2
st


### Sample Output 4

0