Вы воин, который собирается победить бога Тора.
Тор бросил вам вызов, предложив вам решить следующую задачу:
В ряд находится \(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\). Затем, каждый мячик упадет в какую-то ямку. Найдите максимальное количество мячиков, которое окажется в какой-то ямке. После ответа на запрос, мячики пропадают и не учитываются в следующих запросах.