시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 6 | 4 | 3 | 75.000% |
Rikka is now organizing a new year's party for the algorithm association. She has invited $n$ actors from $26$ different groups, represented by lowercase letters. Rikka wants to select some actors among them for the opening show.
Now, the $n$ actors are in a row. The $i$-th actor is from the $s_i$-th group. Rikka decides to choose a non-empty range $[l,r]\ (1 \leq l \leq r \leq n)$ and lets all actors in this range join in the opening show.
Rikka has prepared $26$ different actions. Suppose the range $[l,r]$ has been determined, the opening show will proceed in the following way:
For example, if $5$ players from groups "abacb" are selected, they will chose actions $1,2,1,3,2$ respectively.
Rikka finds that different ranges may sometimes result in the same show. For example, if there are $6$ players and they are from "abacbc" respectively, range $[1,3]$ and $[4,6]$ will result in the same show.
Given string $s$, Rikka wants you to calculate the number of different possible shows.
The first line contains a single integer $n\ (1 \leq n \leq 10^5)$, the number of actors.
The second line contains a lowercase string $s$ of length $n$. $s_i$ represents the group of the $i$-th actor.
Output a single line with a single integer, the number of different possible shows.
5 ababc
7
6 abacbc
10
11 ababcdcefef
33
For the first sample, there are $7$ different possible shows: