你是一名与机神托尔作战的战士。
托尔挑战你解决以下问题:
有 $$$n$$$ 个输送机排成一行,编号从左到右为从 $$$1$$$ 到 $$$n$$$ 的整数。每个传送带都有一个符号“<”或“">”。传送带$$$i$$$的初始状态等于字符串$$$s$$$的第$$$i$$$个字符。有 $$$n+1$$$ 个孔,编号为从 $$$0$$$ 到 $$$n$$$ 的整数。孔 $$$0$$$ 位于传送带 $$$1$$$ 的左侧,对于所有 $$$i \geq 1$$$,孔 $$$i$$$ 位于传送带 $$$i$$$ 的右侧。
当球位于传送带 $$$i$$$ 上时,球按以下规则移动:
如果符号“<”位于传送带 $$$i$$$ 上,则:
- 如果 $$$i=1$$$,则球落入 $$$0$$$ 洞中。
- 如果符号“<”位于传送带 $$$i-1$$$ 上,则球将移动到传送带 $$$i-1$$$。
- 如果符号 ">" 位于传送带 $$$i-1$$$ 上,则球落入孔 $$$i-1$$$ 中。
如果符号 ">" 位于传送带 $$$i$$$ 上,则:
- 如果$$$i=n$$$,则球落入$$$n$$$ 洞中。
- 如果符号 ">" 位于传送带 $$$i+1$$$ 上,则球将移动到传送带 $$$i+1$$$。
- 如果符号“<”位于传送带 $$$i+1$$$ 上,则球落入孔 $$$i$$$ 中。
您应该回答接下来的 $$$q$$$ 查询,每个查询由一对整数 $$$l, r$$$ 定义 ($$$1 \leq l \leq r \leq n$$$):
- 首先,对于所有传送带 $$$l,l+1,...,r$$$,符号“<”更改为“">”,反之亦然。这些更改保留用于下一个查询。
- 之后,在每个传送带 $$$l,l+1,...,r$$$ 上放一个球。然后,每个球都会落入某个洞中。求一洞中的最大球数。查询后,所有球都会消失,并且不会在下一个查询中考虑。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \le n \le 5 \times 10^5 、 1 \le q \le 10^5$$$)。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。它由字符“<”和“>”组成。
接下来的 $$$q$$$ 行包含查询的描述,其中第 $$$i$$$ 包含两个整数 $$$l$$$、$$$r$$$ $$$(1 \le l \le r \le n)$$$,描述第 $$$i$$$ 查询。
输出
打印 $$$q$$$ 行,在第 $$$i$$$ 行中打印第 $$$i$$$ 查询的答案。
示例
输入 #1
5 6 ><>>< 2 4 3 5 1 5 1 3 2 4 1 5
输出 #1
3 3 5 3 2 3
注意
- 在第一个查询中,传送带更改为“>><<<”。之后,在每个传送带上放一个球$$$\{2,3,4\}$$$。三个球全部落入 $$$2$$$ 洞中。所以答案是$$$3$$$。
- 在第二个查询中,传送带更改为 ">>>>>"。之后,在每个传送带上放一个球$$$\{3,4,5\}$$$。三个球全部落入 $$$5$$$ 洞中。所以答案是$$$3$$$。
- 在第三个查询中,传送带更改为“<<<<<”。之后,在每个传送带上放一个球$$$\{1,2,3,4,5\}$$$。所有五个球都落入洞 $$$0$$$ 中。所以答案是$$$5$$$。
- 在第四个查询中,传送带更改为 ">>><<"。之后,在每个传送带上放一个球$$$\{1,2,3\}$$$。三个球全部落入 $$$3$$$ 洞中。所以答案是$$$3$$$。
- 在第五个查询中,传送带更改为“"><<><”。之后,在每个传送带上放一个球$$$\{2,3,4\}$$$。两个球落入 $$$1$$$ 洞,一个球落入 $$$4$$$ 洞。所以,答案是$$$2$$$。
- 在第六个查询中,传送带更改为“<>><>”。之后,在每个传送带上放一个球$$$\{1,2,3,4,5\}$$$。 3 个球落入 $$$3$$$ 洞,1 个球落入 $$$0$$$ 洞,1 个球落入 $$$5$$$ 洞。所以,答案是$$$3$$$。