← 返回题目列表

AtCoder · typical90_cf

084. 有两种类型的字符(★3)

中文机器翻译题面 查看原题

配点: 3 点

問題文

o 和 按字典顺序比较 x 组成的长度 N 的字符串 S 。 对于

满足以下所有条件的一组整数 关于 (l, r) 的编号。 它是

  • 1 \leq l \leq r \leq N
  • S 可以得到第 l 从第一个字符开始 r 个字符之前的区间内, 包含o 和 按字典顺序比较 x 两者 即使选择

制約

  • 1 \leq N \leq 10^6
  • S 是 您也可以写 o, x 组成的长度 N 除

入力

输入是按以下格式从标准输入给出的。

N
S

出力

请打印答案。 到达


入力例 1

4
ooxo

出力例 1

5

(l, r) = (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 可以得到第 5 满足条件。


入力例 2

5
oxoxo

出力例 2

10

入力例 3

5
ooooo

出力例 3

0

什么 (l, r) 也无法满足条件。


入力例 4

7
xxoooxx

出力例 4

16