CF1371F.Raging Thunder

You are a warrior fighting against the machine god Thor.

Thor challenge you to solve the following problem:

There are $n$ conveyors arranged in a line numbered with integers from $1$ to $n$ from left to right. Each conveyor has a symbol "<" or ">". The initial state of the conveyor $i$ is equal to the $i$-th character of the string $s$. There are $n+1$ holes numbered with integers from $0$ to $n$. The hole $0$ is on the left side of the conveyor $1$, and for all $i \geq 1$ the hole $i$ is on the right side of the conveyor $i$.

When a ball is on the conveyor $i$, the ball moves by the next rules:

If the symbol "<" is on the conveyor $i$, then:

• If $i=1$, the ball falls into the hole $0$.
• If the symbol "<" is on the conveyor $i-1$, the ball moves to the conveyor $i-1$.
• If the symbol ">" is on the conveyor $i-1$, the ball falls into the hole $i-1$.

If the symbol ">" is on the conveyor $i$, then:

• If $i=n$, the ball falls into the hole $n$.
• If the symbol ">" is on the conveyor $i+1$, the ball moves to the conveyor $i+1$.
• If the symbol "<" is on the conveyor $i+1$, the ball falls into the hole $i$.

You should answer next $q$ queries, each query is defined by the pair of integers $l, r$ ($1 \leq l \leq r \leq n$):

• First, for all conveyors $l,l+1,...,r$, the symbol "<" changes to ">" and vice versa. These changes remain for the next queries.
• After that, put one ball on each conveyor $l,l+1,...,r$. Then, each ball falls into some hole. Find the maximum number of balls in one hole. After the query all balls disappear and don't considered in the next queries.

你是一名战士，正在与机器之神索尔作战。

索尔向你发起如下挑战：

有 $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, \dots, r$，将符号 "<" 变为 ">"，">" 变为 "<"。这些更改在后续查询中持续生效。
• 然后，在每条传送带 $l, l+1, \dots, r$ 上各放置一个球。随后，每个球均会落入某个洞中。求所有洞中球数的最大值。查询结束后，所有球消失，不参与后续查询。

The first line contains two integers $n$, $q$ ($1 \le n \le 5 \times 10^5 , 1 \le q \le 10^5$).

The second line contains a string $s$ of length $n$. It consists of characters "<" and ">".

Next $q$ lines contain the descriptions of the queries, $i$-th of them contains two integers $l$, $r$ $(1 \le l \le r \le n)$, describing the $i$-th query.

第一行包含两个整数 $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$ 个查询。

Print $q$ lines, in the $i$-th of them print the answer to the $i$-th query.

输出 $q$ 行，其中第 $i$ 行输出第 $i$ 个查询的答案。

• In the first query, the conveyors change to ">><<<". After that, put a ball on each conveyor ${2,3,4}$. All three balls fall into the hole $2$. So the answer is $3$.

• In the second query, the conveyors change to ">>>>>". After that, put a ball on each conveyor ${3,4,5}$. All three balls fall into the hole $5$. So the answer is $3$.

• In the third query, the conveyors change to "<<<<<". After that, put a ball on each conveyor ${1,2,3,4,5}$. All five balls fall into the hole $0$. So the answer is $5$.

• In the fourth query, the conveyors change to ">>><<". After that, put a ball on each conveyor ${1,2,3}$. All three balls fall into the hole $3$. So the answer is $3$.

• In the fifth query, the conveyors change to "><<><". After that, put a ball on each conveyor ${2,3,4}$. Two balls fall into the hole $1$, and one ball falls into the hole $4$. So, the answer is $2$.

• In the sixth query, the conveyors change to "<>><>". After that, put a ball on each conveyor ${1,2,3,4,5}$. Three balls fall into the hole $3$, one ball falls into the hole $0$ and one ball falls into the hole $5$. So, the answer is $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$，一个球落入洞 $0$，一个球落入洞 $5$。因此答案为 $3$。