Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Wedding Day

By Nafis_Shhriar · Limits 1s, 512 MB

Finally, Mr. Akela is getting married. He is very happy. His house is completely decorated with lights. When he saw the lights he was a bit disappointed as there were some consecutive lights off and some were on.

He wanted them to be in more organized manner. He doesn't want any two adjacent light to be in the same state as both off or both on.

Mr. Akela may need to change the state of some lights.

But he is very busy to look after this matter (come on it's his wedding day). So he has given you the job, you will give the instructions to the technician.

There are N lights in the whole decoration system in a single wire (each light is adjacent to the previous and next one but the first light and the last light are not adjacent). You will give the technician Q instructions as change the state of ith light. The state of a light may be changed more than once.

After each instruction you want to know what is the minimum number of lights whose state you have to change. Remember after an instruction Qi, the state of Qi-th light is changed and it remains changed until it's changed by another instruction again.


The first line of input contains an integer N, the number of lights.

The next line will contain a string S, Containing only 0's and 1's. If Si is 0 then the i-th light is off, otherwise it's on.

The next line will contain Q, the number of instructions.

Next Q lines will contain an integer Qi each, as an instruction to change the state of Qith light.


1 ≤ N, Q ≤ 100000

1 ≤ Qi ≤ N


For each query print a single integer X, the minimum number of lights whose state is needed to be changed so that any two adjacent lights are not in the same state.





    72% Solution Ratio

    monna4335Earliest, 1M ago

    Uosmoy383Fastest, 0.0s

    shojib_muLightest, 782 kB

    EmonIIT49JUShortest, 487B


    Login to submit