F. Яростный гром
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы воин, который собирается победить бога Тора.

Тор бросил вам вызов, предложив вам решить следующую задачу:

В ряд находится $$$n$$$ конвееров, пронумерованных целыми числами от $$$1$$$ до $$$n$$$ слева направо. Каждый конвеер показывает один из двух символов «<» или «>». Начальное состояние конвеера $$$i$$$ задается $$$i$$$-м символом строки $$$s$$$. Всего есть $$$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$$$).

Во второй строке находится строка $$$s$$$ длины $$$n$$$. Она состоит их символов «<» и «>».

В следующих $$$q$$$ строках содержится описание запросов, $$$i$$$-я из этих строк содержит два целых числа $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$, описывающих $$$i$$$-й запрос.

Выходные данные

Выведите $$$q$$$ строк, в $$$i$$$-й строке выведите ответ на $$$i$$$-й запрос.

Пример
Входные данные
5 6
><>><
2 4
3 5
1 5
1 3
2 4
1 5
Выходные данные
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$$$, один мячик упал в ямку $$$0$$$ и еще один мячик упал в ямку $$$5$$$. Поэтому ответ равен $$$3$$$.