← 返回题目列表

Codeforces · 45/C

C. 舞蹈课

中文机器翻译题面 查看原题

有 n 个人在上舞蹈课。每个人的舞蹈技能都有其特点。课程开始时,他们从左到右排队。当队列中至少有一对男孩和女孩时,重复以下过程:彼此相邻、舞蹈技巧差异最小的男孩和女孩开始跳舞。如果有几对这样的情侣,则从左边第一个开始跳舞。当一对情侣离开去跳舞后,队列再次闭合,也就是说,队列始终是连续的。舞蹈技巧的差异被理解为ai变量的差异的绝对值。你的任务是找出哪些配对以及以什么顺序开始跳舞。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 人数。下一行包含 n 个符号 B 或 G,不带空格。 B代表男孩,G代表女孩。第三行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 107) — 舞蹈技能。人们按照排队的顺序从左到右指定。

输出

打印结果对 k 的数量。然后打印 k 行,每行包含两个数字——组成这对夫妇的人数。人员从左到右用 1 到 n 的整数进行编号。当一对情侣离开去跳舞时,你不应该重新编号。一对中的数字应按升序排序。按照情侣出发去跳舞的顺序打印出他们。

示例

输入 #1

4
BGBG
4 2 4 3

输出 #1

2
3 4
1 2

输入 #2

4
BBGG
4 6 1 5

输出 #2

2
2 3
1 4

输入 #3

4
BGBB
1 1 2 3

输出 #3

1
1 2