P1878 Dance Class

There are $n$ people attending a dance class. Each person’s dance skill is represented by an integer. At the beginning of the class, they stand in a line from left to right. Whenever there is at least one adjacent opposite-gender pair in the line, the pair with the smallest difference in dance skill will leave the line to start dancing. If multiple pairs have the same minimal difference, the leftmost such pair leaves. After a pair leaves, the gap in the line is closed while preserving the original order (that is, if the line is `ABCD`, then after `BC` leaves, the line becomes `AD`). Here, “smallest difference” means the absolute difference of their skill values is minimal, i.e., minimize $|a_i - a_j|$. Your task is to simulate the process and determine the dancing pairs and their order.

The first line contains a positive integer $n$ denoting the number of people in the line. The second line contains $n$ characters `B` or `G`, where `B` denotes a boy and `G` denotes a girl. The third line contains $n$ integers $a_i$. All information is given in left-to-right order.

The first line contains an integer $k$ denoting the total number of pairs that leave the line. Then output $k$ lines, each containing two integers. Print the pairs in the order they start dancing; each line contains the indices of the two partners (numbered from $1$ to $n$ in the left-to-right input order). Print the smaller index first, then the larger.

For $50\%$ of the testdata, $1 \le n \le 200$. For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $0 \le a_i \le 10^7$. Translated by ChatGPT 5