Восьминiг

Нещодавно Петрик повернувся додому з вiдпочинку на морi. Петрик дуже любить тварин, а тому бiльш за все цей вiдпочинок запам’ятався йому саме їх великою кiлькiстю. Серед них була i його найулюбленiша — восьминiг.

Повернувшись додому, Петрик одразу ж захотів побудувати багато восьминогів. Для цього він вирішив використовувати свій конструктор. Конструктор являє собою набір гнучких паличок, якими можна з’єднувати диски. Кожен з n дисків має ai отворів, у які можна вставляти палички. Паличка не може з’єднувати диск з самим собою та будь-яку пару дисків може з’єднувати не більше однієї палички.

В уявленні Петрика, восьминіг виглядає наступним чином

• тіло восьминога складається с трьох або більше дисків, з’єднаних по колу паличками;

• щупальце восьминога складається з декількох дисків, з’єднаних між собою паличками; щупальце може розгалужуватись та не може зростатись;

• кожне щупальце приєднується до якогось диску у тілі восьминога однією паличкою;

Зверніть увагу, що у восьминога може бути декілька щупалець, а може і навпаки не бути жодного щупальця. Більш того, декілька щупалець можуть бути приєднані до одного диска у тілі. На малюнку показані деякі восьминоги.

Завдання

Допоможіть Петрику скласти восьминогів, щоб виконувались наступні умови:

• для побудови були використані усі диски;

• кожен отвір кожного диску був заповнений паличкою;

• кількість побудваних восьминогів була б максимально можливою. Зверніть увагу, що цей пункт є обов'язковим тільки у деяких підзадачах.

Вхідні дані

У першому рядку вхідного файла задано одне число $n$ ($1\le n\le 10^5$) — кількість дисків у конструкторі Петрика.

У другому рядку записано $n$ цілих чисел $a_i$ ($1\le a_i<n$) — кількість отворів у i-му диску.

Третій рядок містить одне ціле число $maximize$, яке дорівнює $0$, якщо не треба максимізувати кількість восьминогів, і $1$ в противному випадку.

Вихідні дані

У перший рядок вихідного файлу виведіть «Yes», якщо можна побудувати восьминогів, i «No» в противному випадку. У випадку позитивної відповіді виведіть число $c$ — кількість восьминогів. Далі виведіть $n$ рядків. На $i$-му з них запишіть два цілих числа $nu{m}_i$ ($1\le nu{m}_i\le c$), $p_i$ — номер восьминога, якому належить диск $i$, та номер сусіднього диску, який знаходиться ближче до тіла восьминога. Якщо диск $i$ належить тілу, будемо вважати, що $p_i=-1$.

Для кращого розуміння ознайомтесь з прикладами із умови.

Приклади

Примітка

Перший приклад з умови вiдповiдає першому восьминогу на малюнку, а другий — другому та третьому.

Звернiть увагу, що для даних прикладiв можливi i iншi схеми, задоволняючi усiм необхiдним вимогам.

Оцінювання

1. ($9$ балів): Для всіх $i$ виконується $a_i\in \{1,3\}$. Максимiзацiя кiлькостi восьминогiв не потрібна.

2. ($13$ балів): Для всіх $i$ виконується $a_i\in \{1,3\}$. Максимiзацiя кiлькостi восьминогiв потрібна.

3. ($27$ балів): Максимiзацiя кiлькостi восьминогiв не потрібна.

4. ($51$ бал): Максимiзацiя кiлькостi восьминогiв потрібна.