CF1371F Raging Thunder

你是一名战士，正在与机械之神 Thor 战斗。 Thor 向你提出了如下挑战： 有 $n$ 个传送带排成一行，从左到右编号为 $1$ 到 $n$。每个传送带上有一个符号 “”。第 $i$ 个传送带的初始状态等于字符串 $s$ 的第 $i$ 个字符。共有 $n+1$ 个洞，编号为 $0$ 到 $n$。洞 $0$ 在第 $1$ 个传送带的左侧，对于所有 $i \geq 1$，洞 $i$ 在第 $i$ 个传送带的右侧。 当一个小球在第 $i$ 个传送带上时，小球按照以下规则移动： 如果第 $i$ 个传送带上的符号是 “”，则： - 如果 $i=n$，小球掉入洞 $n$。 - 如果第 $i+1$ 个传送带上的符号是 “>”，小球移动到第 $i+1$ 个传送带。 - 如果第 $i+1$ 个传送带上的符号是 “” 变为 “

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 5 \times 10^5, 1 \leq q \leq 10^5$）。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 “” 组成。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），描述第 $i$ 个询问。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

- 第一个询问后，传送带变为 “>>>>>”。然后在 $\{3,4,5\}$ 号传送带各放一个小球，三个小球都掉入洞 $5$，所以答案为 $3$。 - 第三个询问后，传送带变为 “