题解

题目概述

题目要求统计一个字符串中所有满足条件的非空子串数量。条件是：子串去重后，其字符按照相对顺序排列在字典序上是一个单调递增的字符串。

例如，字符串 aabca 去重后为 abc，满足字典序单调递增，因此 aabca 是一个好字符串。我们需要计算所有这样的子串数量。

解题思路

1. 去重与字典序：子串去重后，字符按照它们在原字符串中的顺序排列，且必须满足字典序递增。这意味着去重后的子串中的字符必须是严格递增的。
2. 子串的贡献：对于每个字符 s[left]，我们需要找到以它为左端点的所有满足条件的子串。这些子串的右端点必须满足以下条件：

题目内容

小红认为一个字符串是好字符串当且仅当这个字符串去重后按照相对顺序排列在字典序上是一个单调递增字符串。

例如: $s=aabca$，去重后为$abc$，满足字典序单调递增。

现在小红有一个长度为$n$的字符串$t$，请你帮助她计算有多少个非空子串是好字符串。

去重:每种字符只保留第一个出现的位置。

子串:子串是指一个字符串中的连续部分。

输入描述

第一行一个整数$n(1 ≤n≤10^5)$，表示字符串长度。

第二行一个长度为$n$的字符串$t$，保证输入只含小写字母。

输出描述

一个整数，表示$t$中有多少个子串是好字符串。

样例1

输入

5
aabca

输出

13