Алисия и Беатрис готовят фокус для шоу талантов IOI. Фокус работает следующим образом:

• Доброволец выбирает перестановку $P$ длины $N$ и выкладывает $N$ карт на стол. Карты пронумерованы от $0$ до $N - 1$, при этом на карте $i$ написано значение $P[i]$.
• Алисия входит в комнату, осматривает карты и выбирает $K$ из них, чтобы перевернуть рубашкой вверх, скрыв их значения.
• Затем в комнату входит Беатрис, видит текущее расположение карт (включая то, какие из них перевернуты рубашкой вверх) и магическим образом определяет значения всех $K$ скрытых карт!

Ваша задача — разработать и реализовать стратегию для Алисии и Беатрис. Чем эффектнее фокус, тем выше ваш балл: цель состоит в том, чтобы максимизировать $K$, количество скрытых карт, которые Беатрис может правильно угадать.

Детали реализации

Первая процедура, которую вам нужно реализовать:

std::vector<int> Alicia(std::vector<int> P)

• $P$: массив длины $N$, представляющий выбранную перестановку.

Эта процедура должна возвращать массив $Q$ длины $N$, представляющий действия Алисии по переворачиванию карт. Для каждого индекса $i$ ($0 \le i \le N - 1$) значения в $Q$ должны быть установлены следующим образом: $Q[i] = -1$, если Алисия переворачивает карту $i$, и $Q[i] = P[i]$ в противном случае.

Вторая процедура, которую вам нужно реализовать:

std::vector<int> Beatriz(std::vector<int> Q)

• $Q$: массив длины $N$, возвращенный функцией Alicia. Этот массив определяет конфигурацию карт, когда входит Беатрис.

Эта процедура должна возвращать массив $B$ длины $N$, представляющий исходную перестановку $P$, то есть для каждого $i$ ($0 \le i \le N - 1$) должно выполняться $B[i] = P[i]$.

В каждом тестовом случае обе процедуры вызываются ровно один раз следующим образом:

• Во время первого запуска программы:
  • Alicia вызывается с исходной перестановкой $P$.
  • Для массива $Q$, возвращенного Alicia:
    • Если массив не соответствует описанным выше ограничениям, вы получаете вердикт Output isn't correct.
    • В противном случае массив $Q$ сохраняется тестирующей системой.
• Во время второго запуска программы:
  • Beatriz вызывается с массивом $Q$.

Ограничения

• $N = 256$
• $1 \le P[i] \le N$ для каждого $i$ такого, что $0 \le i < N$.
• Все значения в $P$ различны.

Подзадачи

Пусть $M$ — минимальное значение $K$, при котором ваше решение успешно выполняет фокус во всех тестовых случаях.

• Если $M = 0$ или ваше решение не может правильно восстановить перестановку $P$ в любом из тестовых случаев, вы получаете 0 баллов.
• В противном случае ваш балл равен: $$\min(20 + 5 \cdot M, 100)$$

В частности, максимальный балл достигается при $M = 16$.

Примеры

Рассмотрим сценарий, где $N = 6$ и $P = [2, 4, 3, 1, 5, 6]$. Процедура Alicia вызывается следующим образом:

Alicia([2, 4, 3, 1, 5, 6])

Предположим, Алисия использует следующую стратегию: перевернуть каждую карту $i$ такую, что $P[i] = i + 1$. В этом случае условие выполняется для $i = 2, 4$ и $5$. Следовательно, процедура возвращает массив $[2, 4, -1, 1, -1, -1]$.

Теперь процедура Beatriz вызывается следующим образом:

Beatriz([2, 4, -1, 1, -1, -1])

Зная стратегию Алисии, она находит и возвращает исходный массив $P = [2, 4, 3, 1, 5, 6]$.

В этом случае $K = 3$, так как были перевернуты три карты. Однако, если отправить такое решение, оно получит 0 баллов, потому что существуют перестановки, в которых ни один индекс $i$ не удовлетворяет условию $P[i] = i + 1$.

Примечание: этот пример не удовлетворяет ограничению $N = 256$ и поэтому не будет использоваться при оценивании. Загружаемое приложение к этой задаче включает пример входных данных для проверяющей программы с $N = 256$. Та же перестановка $P$ используется в подзадаче 0 во время оценки.

Проверяющая программа

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

N
P[0] P[1] ... P[N-1]

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

S
Q[0] Q[1] ... Q[S-1]
T
B[0] B[1] ... B[T-1]

Здесь: $S$ — длина массива $Q$, возвращенного Alicia. $T$ — длина массива $B$, возвращенного Beatriz.

Обратите внимание, что хотя $N = 256$ выполняется для всех тестовых случаев в этой задаче, вы можете использовать проверяющую программу с любым значением $N$.