Петя занимается игрой на гитаре с малых лет и уже освоил почти все известные ему приемы игры на ней. В поисках достойного испытания для его недюжинных способностей Петя наткнулся на компьютерную игру «Виртуоз гитары».
В этой игре Пете дается маленькая игрушечная гитара, на которой есть всего две струны, и игрок должен исполнить композицию, состоящую из n нот. На каждой струне можно сыграть только одну из семи нот: от «до» до «си».
К счастью, Петя настолько наловчился играть в данную игру, что в перерыве между воспроизведением нот может чуть-чуть донастроить одну из струн на одну ноту выше или ниже. Однако он не может натягивать струну, если данная струна уже играет ноту «си», чтобы не порвать ее; и не может слишком сильно струну ослаблять, если струна уже играет ноту «до». Таким образом, Петя всегда остается в пределах одной октавы (ноты от «до» до «си»).
Поиграв так немного, Петя дошел до самого высокого уровня сложности и наткнулся на очень сложную мелодию. Напишите программу, определяющую по данной последовательности из n нот, сможет ли он исполнить эту композицию, и, если да, то какие струны нужно будет перенастраивать между исполнением нот. Перед началом своего выступления Петя может настроить струны на своей гитаре на любые ноты от «до» до «си» в пределах одной октавы.
В первой строке входных данных задано число n (1 ≤ n ≤ 200 000) — количество нот в композиции.
Во второй строке даны n целых чисел от 1 до 7 — ноты. Число 1 обозначает ноту «до», 2 — «ре», 3 — «ми», 4 — «фа», 5 — «соль», 6 — «ля», 7 — «си».
В первой строке выходных данных требуется вывести «YES», если данную мелодию можно исполнить, и «NO», если нельзя.
В случае, если мелодию можно сыграть, то в следующих n строках должны быть записаны пары чисел — на какие ноты настроена первая и вторая струна перед исполнением i-й ноты.
Если существует несколько правильных решений, необходимо вывести любое из них.
7
1 2 3 4 5 6 7
YES
3 1
3 2
3 1
4 1
5 1
6 1
7 1
4
1 3 7 2
NO
