Непустая строка из цифр является разнообразной, если количество вхождений каждого символа в неё не превосходит количество различных символов в ней.
Например,
- строка «7» разнообразная, так как 7 встречается в ней \(1\) раз, и количество различных символов в ней равно \(1\);
- строка «77» не является разнообразной, так как 7 встречается в ней \(2\) раза, а количество различных символов в ней равно \(1\);
- строка «1010» разнообразная, так как 0 и 1 встречаются в ней по \(2\) раза, и количество различных символов в ней равно \(2\);
- строка «6668» не является разнообразной, так как 6 встречается в ней \(3\) раза, а количество различных символов в ней равно \(2\).
Вам дана строка \(s\) длины \(n\), состоящая из цифр от \(0\) до \(9\). Найдите, сколько из ее \(\frac{n(n+1)}{2}\) подстрок являются разнообразными.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Обратите внимание, что если некоторая разнообразная строка встречается в \(s\) несколько раз, то каждое её вхождение должно быть подсчитано независимо. Например, в строке «77» есть две разнообразных подстроки, равных «7», поэтому ответ для строки «77» равен \(2\).
Выходные данные
Для каждого набора входных данных выведите одно число: количество разнообразных подстрок строки \(s\).
Примечание
В первом наборе входных данных подстрока «7» разнообразная.
Во втором наборе входных данных подстрока «7» разнообразная. Так как она встречается дважды, ответ равен \(2\).
В третьем наборе входных данных следующие подстроки являются разнообразными: «0» (\(2\) вхождения), «01», «010», «1» (\(2\) вхождения), «10» (\(2\) вхождения), «101» и «1010».
В четвёртом наборе входных данных следующие подстроки являются разнообразными: «0» (\(3\) вхождения), «01», «011», «0110», «1» (\(2\) вхождения), «10», «100», «110» и «1100».
В пятом наборе входных данных следующие подстроки являются разнообразными: «3», «39», «399», «6», «9» (\(4\) вхождения), «96» и «996».
В шестом наборе входных данных все \(15\) непустых подстрок строки «23456» являются разнообразными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798
|
1
2
10
12
10
15
106
|