## Editorial for Another Random Contest 1 P4 - Bracket Query

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Observations

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

Let's denote all `(`

as and all `)`

as . 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:**

#### 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 , .

**Time Complexity:**

## Comments