Пиратские катакомбы на острове Сокровищ были вырыты по следующему принципу. После скрытого входа расположена пещера, из которой выходят два туннеля - налево и направо. Каждый из туннелей заканчивается пещерой, из которой так же выходит два туннеля, и т. д. Длина каждого туннеля равна единице. Конечные пещеры, которые находятся на расстоянии D от входа, не имеют дальнейших выходов. Никакие туннели между собой не пересекаются, и не ведут к одной пещере. Число D называют глубиной катакомб.

В каждой из конечных пещер спрятан один сундук с сокровищами. Перед прибытием на остров Капитана Джека Воробья пираты решили переместить эти сундуки в соответствии с последними указаниями Капитана. Пираты нарисовали план катакомб и пронумеровали конечные пещеры слева направо. Потом для каждого сокровища был установлен номер пещеры, в которой он должен оказаться перед прибытием Капитана. После перемещения в каждой пещере снова окажется только один сундук.

Чтобы обеспечить безопасность сокровищ, пираты могут только обменивать между собой сундуки из двух пещер. Только после окончания одного обмена можно начинать другой. Необходимо найти наименьшее суммарное расстояние, которое пиратам необходимо будет нести сундуки, чтобы разместить их требуемым образом.

Входные данные

Первая строка содержит одно целое число D - глубину катакомб (D ≤ 8). Вторая строка содержит 2D разных целых чисел от 1 до 2D. Каждое i-ое из них идентифицирует номер пещеры, в которую должен попасть сундук, находившийся сначала в пещере i.

Выходные данные

Первая строка содержит одно целое число - минимальное суммарное расстояние, которое пройдут пираты с сокровищами. Вторая строка содержит целое число K - соответствующее количество обменов. Каждая следующая из K строк содержит два числа, являющимися номерами пещер, между которыми происходит обмен. Обмены должны быть указаны в том порядке, в котором они должны происходить.

Объяснение к примеру

Сначала поменяем местами сокровища в пещерах 3 и 4. Пройдено расстояние 4 (по 2 для каждого сундука). Потом поменять сокровища в пещерах 4 и 1, и 3 и 2. Расстояние в обоих случаях – 8. Таким образом – все станут на свои места, а суммарное расстояние будет