Осьминог

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

Вернувшись домой, Петрик захотел построить множество осьминогов, используя свой конструктор. Конструктор состоит из набора гибких палочек, которые можно вставлять в отверстия на дисках. Каждый из n дисков имеет a[i] отверстий. Палочка не может соединять диск с самим собой, и любую пару дисков можно соединить не более чем одной палочкой.

По представлению Петрика, осьминог выглядит следующим образом:

• Тело осьминога состоит из трех или более дисков, соединенных по кругу палочками.

• Щупальце осьминога состоит из нескольких дисков, соединенных палочками; оно может разветвляться, но не может срастаться.

• Каждое щупальце присоединяется к какому-то диску в теле осьминога одной палочкой.

Обратите внимание, что у осьминога может быть несколько щупалец или вообще не быть ни одного. Более того, несколько щупалец могут быть присоединены к одному диску в теле. На рисунке показаны некоторые примеры осьминогов.

Задача

Помогите Петрику собрать осьминогов так, чтобы выполнялись следующие условия:

• Были использованы все диски.

• Каждое отверстие каждого диска было заполнено палочкой.

• Количество построенных осьминогов было максимально возможным. Этот пункт обязателен только в некоторых подзадачах.

Входные данные: В первой строке входного файла задано одно число n (1 ≤ n ≤ 10^5) — количество дисков в конструкторе Петрика.

Во второй строке записано n целых чисел a[i] (1 ≤ a[i] < n) — количество отверстий в i-м диске.

Третья строка содержит одно целое число maximize, которое равно 0, если не нужно максимизировать количество осьминогов, и 1 в противном случае.

Выходные данные: В первой строке выходного файла выведите «Yes», если можно построить осьминогов, и «No» в противном случае. В случае положительного ответа выведите число c — количество осьминогов. Далее выведите n строк. На i-й из них запишите два целых числа num[i] (1 ≤ num[i] ≤ c), p[i] — номер осьминога, которому принадлежит диск i, и номер соседнего диска, который находится ближе к телу осьминога. Если диск i принадлежит телу, будем считать, что p[i] = -1.

Для лучшего понимания ознакомьтесь с примерами из условия.

Примеры

Оценивание