题目描述

给定长度为 n 的字符串 s（只包含字符 r、e、d），定义任何下标 i<j<k 且 s[i]='r', s[j]='e', s[k]='d' 的子序列 “red” 的权值为

|i-j| + |i-k| + |j-k|

计算所有这样的子序列权值之和。

解题思路

1. 化简权值公式

题目内容

小红有一个长度为n的字符串$s=s_1s_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_1 S_2 S_4$权值为

$|1-2|+|1-4|+|2-4| =6$。

样例2

输入

7
redeeed

输出

52