Танцевальный кружок посещает n человек. Каждый человек характеризуется своим умением танцевать ai. В начале занятия они выстраиваются в линию слева направо. Пока в линии присутствует хоть одна пара мальчик и девочка, повторяется следующий процесс: стоящие рядом мальчик и девочка, имеющие минимальную разницу умений, отправляются танцевать. Если таких пар несколько, танцевать отправляется самая левая пара. После того как ушла очередная пара, линия снова замыкается, т. е. получается, что линия всегда непрерывна. Под разницей умений имеется в виду модуль разности величин a двух танцоров. Ваша задача — узнать, какие пары и в каком порядке отправятся танцевать.
Выходные данные
Выведите количество получившихся пар k. Далее выведите k строк по два числа в каждой — номера людей, входящих в очередную пару. Люди нумеруются целыми числами от 1 до n слева направо. Когда уходит очередная пара, перенумеровывать людей не нужно. Номера в одной паре упорядочивайте по возрастанию. Пары выводите в том порядке, в котором они отправляются танцевать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
BGBG
4 2 4 3
|
2
3 4
1 2
|
|
2
|
4
BBGG
4 6 1 5
|
2
2 3
1 4
|
|
3
|
4
BGBB
1 1 2 3
|
1
1 2
|