题目内容

给定一个长度为 $n$ 的字符串 $s$，仅由字符 r、e、d 组成。对于任意满足 $1 \le i < j < k \le n$ 且 $s_i$ 为字符 r、$s_j$ 为字符 e、$s_k$ 为字符 d 的三元组 $(i,j,k)$，定义其跨度为 $|i-j|+|j-k|+|i-k|$。请你计算所有这样的三元组的跨度总和。

数据范围：字符串的长度 $n$ 满足 $1 \le n \le 2\times 10^5$，且字符串中仅包含字符 r、e、d。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 2\times 10^5$），表示字符串的长度。 第二行包含一个长度为 $n$ 的字符串，仅由字符 r、e、d 组成。

输出描述