Alicia と Beatriz は、IOI タレントショーに向けて手品を準備しています。この手品は次のように行われます。

• ボランティアが長さ $N$ の順列 $P$ を選択し、$N$ 枚のカードをテーブルに並べます。カードには $0$ から $N - 1$ までの番号が振られており、カード $i$ には値 $P[i]$ が書かれています。
• Alicia が部屋に入り、カードを観察した後、$K$ 枚のカードを選んで裏返し、値を隠します。
• 次に Beatriz が部屋に入り、現在のカードの配置（どのカードが裏返されているかを含む）を見て、裏返された $K$ 枚すべてのカードの値を魔法のように言い当てます！

あなたの課題は、Alicia と Beatriz のための戦略を考案し、実装することです。手品が印象的であればあるほど、スコアは高くなります。目標は、Beatriz が正しく言い当てられる隠されたカードの枚数 $K$ を最大化することです。

実装の詳細

あなたが実装しなければならない最初のプロシージャは以下の通りです。

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

• $P$: 選択された順列を表す長さ $N$ の配列。

このプロシージャは、Alicia が行うカードの裏返しを表す長さ $N$ の配列 $Q$ を返す必要があります。各インデックス $i$ ($0 \le i \le N - 1$) について、$Q$ の値は次のように設定しなければなりません。

• Alicia がカード $i$ を裏返す場合は $Q[i] = -1$
• それ以外の場合は $Q[i] = P[i]$

あなたが実装しなければならない2番目のプロシージャは以下の通りです。

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

• $Q$: Alicia が返した配列。この配列は、Beatriz が部屋に入ったときのカードの構成を指定します。

このプロシージャは、元の順列 $P$ を表す長さ $N$ の配列 $B$ を返す必要があります。つまり、各 $i$ ($0 \le i \le N - 1$) に対して $B[i] = P[i]$ が成り立つ必要があります。

各テストケースにおいて、2つのプロシージャはそれぞれちょうど1回ずつ、以下のように呼び出されます。

• プログラムの最初の実行時:
  • 元の順列 $P$ を引数として Alicia が呼び出されます。
  • Alicia が返した配列 $Q$ について:
    • 配列が上記の制約に従っていない場合、Output isn't correct という判定を受けます。
    • それ以外の場合、配列 $Q$ は採点システムに保存されます。
• プログラムの2回目の実行時:
  • 配列 $Q$ を引数として Beatriz が呼び出されます。

制約

• $N = 256$
• $1 \le P[i] \le N$ （各 $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])

Alicia が「$P[i] = i + 1$ となるすべてのカード $i$ を裏返す」という戦略をとるとします。この場合、条件は $i = 2, 4, 5$ で成り立ちます。したがって、プロシージャは配列 $[2, 4, -1, 1, -1, -1]$ を返します。

次に、プロシージャ Beatriz が次のように呼び出されます。

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

Alicia の戦略を知っている Beatriz は、元の配列 $P = [2, 4, 3, 1, 5, 6]$ を見つけ出し、返します。

この場合、$3$ 枚のカードが裏返されたため $K = 3$ です。しかし、もしこの戦略を提出した場合、$P[i] = i + 1$ を満たすインデックス $i$ が存在しない順列も存在するため、スコアは 0 点となります。

この例は制約 $N = 256$ を満たしていないため、採点には使用されません。この課題のダウンロード可能な添付ファイルには、$N = 256$ の場合のサンプル入力が含まれています。評価時のサブタスク 0 では、同じ順列 $P$ が使用されます。

サンプルグレーダー

入力形式:

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$ は Alicia が返した配列 $Q$ の長さです。
• $T$ は Beatriz が返した配列 $B$ の長さです。

この課題のすべてのテストケースで $N = 256$ が成り立ちますが、サンプルグレーダーは任意の $N$ の値で使用できることに注意してください。