Rikka와 새해 파티

Rikka는 알고리즘 협회의 새해 파티를 준비하고 있다. 그녀는 소문자로 표시되는 26개의 서로 다른 그룹에서 $n$명의 배우를 초대했다. Rikka는 그중 일부를 골라 개막 공연에 세우려고 한다.

이제 $n$명의 배우가 한 줄로 서 있다. $i$번째 배우는 $s_i$번째 그룹 소속이다. Rikka는 공백이 아닌 구간 $[l,r]$ ($1 \leq l \leq r \leq n$)을 고르고, 이 구간의 배우 모두를 개막 공연에 참여시킨다.

공연은 다음 순서로 진행된다.

• 배우들은 순서대로 연기한다. $l$번째 배우가 가장 먼저, $r$번째 배우가 가장 마지막에 연기한다.
• $i$번째 배우는 차례가 되면 다음과 같이 행동을 정한다. 먼저 연기한 배우 $j$ 중 같은 그룹 $s_i$ 소속이 있으면, 그 배우 $j$와 같은 행동을 한다. 없으면 지금까지 아무도 고르지 않은 행동 중 번호가 가장 작은 행동을 고른다.

예를 들어 그룹이 abacb인 5명의 배우는 차례로 행동 $1,2,1,3,2$를 고른다.

Rikka는 서로 다른 구간이 같은 공연을 만들 수 있다는 것을 알아냈다. 예를 들어 그룹이 abacbc인 6명의 배우에서 구간 $[1,3]$과 $[4,6]$은 같은 공연을 만든다.

두 공연은 행동의 개수가 다르거나, 어떤 번호 $i$에서 $i$번째 행동이 다르면 서로 다른 공연이다. 공연은 $s$의 어떤 구간 $[l,r]$이 만들어 낼 수 있을 때 가능하다. $s$가 주어졌을 때, 가능한 서로 다른 공연의 수를 구하라.

첫째 줄에 배우의 수 $n$ ($1 \leq n \leq 10^5$)이 주어진다.

둘째 줄에 길이가 $n$인 소문자 문자열 $s$가 주어진다. $s_i$는 $i$번째 배우의 그룹이다.

가능한 서로 다른 공연의 수를 한 줄에 정수 하나로 출력한다.

첫 번째 예제에서 가능한 서로 다른 공연은 7가지이다.

1. 행동 $1$. 구간 $[1,1]$, $[2,2]$, $[3,3]$, $[4,4]$, $[5,5]$에 해당한다.
2. 행동 $1,2$. 구간 $[1,2]$, $[2,3]$, $[3,4]$, $[4,5]$에 해당한다.
3. 행동 $1,2,1$. 구간 $[1,3]$, $[2,4]$에 해당한다.
4. 행동 $1,2,3$. 구간 $[3,5]$에 해당한다.
5. 행동 $1,2,1,2$. 구간 $[1,4]$에 해당한다.
6. 행동 $1,2,1,3$. 구간 $[2,5]$에 해당한다.
7. 행동 $1,2,1,2,3$. 구간 $[1,5]$에 해당한다.