Collectible Substrings

ZRQ discovered that there are \(N\) mineral blocks arranged in a row. Each block is represented by a lowercase letter and has an associated importance value \(V_i\). ZRQ wants to collect a contiguous segment of these blocks. However, he imposes a strict condition: the chosen substring's lexicographical descending order ranking must be equal to the sum of its importance values.

Note: The lexicographical ranking is determined by sorting all distinct substrings (by content) in descending lexicographical order, and substrings that are the same (even if they occur at different positions) have the same ranking. Nevertheless, when counting collectible substrings, each occurrence (i.e. with different start or end indices) is counted separately provided it meets the condition.

For example, consider \(N = 4\) with the mineral string abcd and importance values 10 0 1 1. All substrings sorted in descending lexicographical order are:

1: d
2: cd
3: c
4: bcd
5: bc
6: b
7: abcd
8: abc
9: ab
10: a

Examine a few substrings:

• The substring d has ranking \(1\) and an importance sum of \(1\), so it can be collected.
• The substring cd has ranking \(2\) and an importance sum of \(2\), so it can be collected.
• The substring a has ranking \(10\) and an importance sum of \(10\), so it can be collected.

Other substrings do not satisfy the condition. Therefore, there are 3 collectible substrings in this example.

Your task is to count the number of collectible substrings in the input string.

inputFormat

The input consists of three parts:

1. An integer \(N\) representing the number of mineral blocks.
2. A string of \(N\) lowercase letters representing the minerals.
3. \(N\) space-separated integers, where the \(i\)-th integer is the importance value \(V_i\) of the \(i\)-th block.

Note: \(N\) is small enough to allow an \(O(N^2)\) solution.

outputFormat

Output a single integer representing the number of substrings (each counted according to its occurrence in the original string) that meet the collectible criteria.

sample

4
abcd
10 0 1 1

3