Codeforces Round 654 (Div. 2) |
---|
Finished |
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 the symbol ">" is on the conveyor $$$i$$$, then:
You should answer next $$$q$$$ queries, each query is defined by the pair of integers $$$l, r$$$ ($$$1 \leq l \leq r \leq n$$$):
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.
Print $$$q$$$ lines, in the $$$i$$$-th of them print the answer to the $$$i$$$-th query.
5 6 ><>>< 2 4 3 5 1 5 1 3 2 4 1 5
3 3 5 3 2 3
Name |
---|