write a go solution for Description:
A binary string is a string where every character is texttt0 or texttt1. Call a binary string decent if it has an equal number of texttt0s and texttt1s.

Initially, you have an infinite binary string t whose characters are all texttt0s. You are given a sequence a of n updates, where a_i indicates that the character at index a_i will be flipped (texttt0arrowtexttt1). You need to keep and modify after each update a set S of disjoint ranges such that:

- for each range [l,r], the substring t_l...t_r is a decent binary string, and
- for all indices i such that t_i=texttt1, there exists [l,r] in S such that l<=i<=r.

You only need to output the ranges that are added to or removed from S after each update. You can only add or remove ranges from S at most mathbf10^6 times.

More formally, let S_i be the set of ranges after the i-th update, where S_0=varnothing (the empty set). Define X_i to be the set of ranges removed after update i, and Y_i to be the set of ranges added after update i. Then for 1<=i<=n, S_i=(S_i-1setminusX_i)cupY_i. The following should hold for all 1<=qi<=qn:

- foralla,binS_i,(aneqb)arrow(acapb=varnothing);
- X_isubseteqS_i-1;
- (S_i-1setminusX_i)capY_i=varnothing;
- displaystylesum_i=1^n(|X_i|+|Y_i|)<=q10^6.

Input Format:
The first line contains a single integer n (1<=n<=2*10^5) — the number of updates.

The next n lines each contain a single integer a_i (1<=a_i<=2*10^5) — the index of the i-th update to the string.

Output Format:
After the i-th update, first output a single integer x_i — the number of ranges to be removed from S after update i.

In the following x_i lines, output two integers l and r (1<=l<r<=10^6), which denotes that the range [l,r] should be removed from S. Each of these ranges should be distinct and be part of S.

In the next line, output a single integer y_i — the number of ranges to be added to S after update i.

In the following y_i lines, output two integers l and r (1<=l<r<=10^6), which denotes that the range [l,r] should be added to S. Each of these ranges should be distinct and not be part of S.

The total number of removals and additions across all updates must not exceed mathbf10^6.

After processing the removals and additions for each update, all the ranges in S should be disjoint and cover all ones.

It can be proven that an answer always exists under these constraints.

Note:
Line breaks are provided in the sample only for the sake of clarity, and you don't need to print them in your output.

After the first update, the set of indices where a_i=1 is 1. The interval [1,2] is added, so S_1=[1,2], which has one texttt0 and one texttt1.

After the second update, the set of indices where a_i=1 is 1,6. The interval [5,6] is added, so S_2=[1,2],[5,6], each of which has one texttt0 and one texttt1.

After the third update, the set of indices where a_i=1 is 1,5,6. The interval [5,6] is removed and the intervals [4,5] and [6,7] are added, so S_3=[1,2],[4,5],[6,7], each of which has one texttt0 and one texttt1.

After the fourth update, the set of indices where a_i=1 is 1,6. The interval [4,5] is removed, so S_4=[1,2],[6,7], each of which has one texttt0 and one texttt1.

After the fifth update, the set of indices where a_i=1 is 1. The interval [6,7] is removed, so S_5=[1,2], which has one texttt0 and one texttt1.. Output only the code with no comments, explanation, or additional text.