Observations

If two insertions are allowed, one can insert a series of left brackets before ~L~ and a series of right brackets after ~R~. It can be shown that it will always generate a valid bracket sequence.

Let's denote all ( as ~1~ and all ) as ~-1~. We can check whether or not we need to add a series of left brackets by checking the signs of prefix sum. If at any point the prefix sum turns negative, we need to add a series of left brackets. The same thing can be applied to check for right brackets by using postfix sum and check for positive instead of negative.

Subtask 1

Simply enumerate through all positions to check if at any position the prefix sum turns negative or postfix sum turns positive. Output NO if both occur, and YES otherwise.

Time Complexity: ~\mathcal O(NQ)~

Subtask 2

Use any data structure that can answer range minimum query (RMQ), such as a segment tree or sparse table, to find the minimum prefix sum and maximum postfix sum in the interval ~L~, ~R~.

Time Complexity: ~\mathcal O((N+Q) \log N)~