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/A

N/A

- 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 $ .