思路

• 对于任意合法的 $i<j<k$，有

• 因此每个 “$red$” 子序列只和其首尾位置相关：权值为 $2\,(k-i)$。
• 令在位置 $j$ 取字母 $e$。设

题目内容

小红有一个长度为 $n$ 的字符串 $s=s_1,s_2,…,s_n$，她定义长度为 $3$ 的子序列 $s_is_js_k$ 的权值为 $|i-j|+|i- k|+|j-k|$ 。

现在，小红希望你计算所有 $“red”$ 子序列的权值之和。

如果字符串 $t=“red”$ 可以通过删除字符串 $s$ 中的若干(可能为零或全部)元素得到，则字符串 $t$ 是字符串 $s$ 的 $“red”$ 子序列。

输入描述

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

第二行输入一个长度为 $n$ ，且只由 $'r'、'e'、'd'$ 三个小写字母

输出描述

在一行上输出一个整数，代表所有 $“red”$ 子序列的权值之和。

样例1

输入

4
reed

输出

12

说明

在该样例中，一共有两个不同的 $“red”$ 子序列：

删除第二个字符得到的子序列 $s_1s_3s_4$ 权值为 $|1-3|+|1-4|+|3-4|=6$；

删除第三个字符得到的子序列 $s_1s_2s_4$ 权值为 $|1-2|+|1-4|+|2-4|=6$ 。

样例2

输入

7
redeeed

输出

52