這是一道互動題。

題目敘述

你迷上了一個解謎遊戲。在遊戲的這一關中，你的任務是打開一個寶箱。

你手中有 $n$ 把鑰匙，編號為 $0\sim n-1$；寶箱上有 $n$ 個凹槽，編號也為 $0\sim n-1$。你的任務是收集相關線索，將鑰匙按特定的順序插入凹槽，然後按動開關打開寶箱。這個正確的鑰匙順序可以視為一個長度為 $n$ 的排列 $p$（下標從 $0$ 開始），代表 $i$ 號凹槽中應當放入 $p_i$ 號鑰匙。

你的嘗試可以視為給出一個長度為 $n$ 的排列 $q$，表示在 $i$ 號凹槽中放入 $q_i$ 號鑰匙。如果對於每個 $0 \le i \le n-1$ 均有 $p_i=q_i$，則說明你的嘗試是正確的，你將打開寶箱並順利通關，否則通關失敗。你只有一次嘗試機會，因此你務必格外謹慎。

經過仔細地觀察，你發現了這個寶箱的奧秘所在：寶箱的後面有一個隱藏的按鈕。當你給出一個排列 $q$ 並相應地將鑰匙放入凹槽之後，你可以按動隱藏按鈕，寶箱將給出有多少把鑰匙放置的位置是正確的——即有多少個 $0 \le i \le n-1$ 滿足 $p_i=q_i$。將你的這一操作稱為一次詢問，你可以在按下最終的開箱開關之前，多次改變你的排列 $q$ 並進行詢問，直到你收集到足夠的資訊能確定答案排列 $p$ 為止。

但出於遊戲難度和趣味性的考慮，還有一條特殊規定：你向寶箱詢問的次數不得超過 $20000$ 次，一旦超過，寶箱將立刻永久上鎖，也就意味著你的遊戲失敗。能不能取得遊戲的成功，就看你的本事了！

實作細節

你不需要，也不應該實作主函式。你需要在程式開頭添加 #include "puzzle.h" 並實作如下函式：

void play(int n);

• 其中，$n$ 表示排列長度。
• 互動庫執行過程中，該函式將會被呼叫恰好一次。

你可以呼叫以下兩個函式：

int query(const std::vector<int> &q);

• 其中，$q$ 應當是一個長度為 $n$ 的排列，即 $q$ 的長度應當為 $n$，且 $0\sim n-1$ 中的所有整數在 $q_{0} \sim q_{n-1}$ 中均恰好出現一次。
• 函式將比較你給出的排列 $q$ 與答案排列 $p$，並返回本次詢問的結果，即有多少個整數 $i$ 滿足 $0 \leq i \leq n-1$ 且 $p_i = q_i$。
• 你呼叫該函式的次數不應當超過 $20000$。

void check(const std::vector<int> &q);

• 其中，$q$ 應當是一個長度為 $n$ 的排列，即 $q$ 的大小應當為 $n$，且 $0\sim n-1$ 中的所有整數在 $q_{0} \sim q_{n-1}$ 中均恰好出現一次。
• 這個函式應當在你的程式執行 play 函式時恰好被執行一次。
• 函式將比較你給出的排列 $q$ 與答案排列 $p$，如果 $p=q$ 則認為你給出的答案正確，否則認為你給出的答案錯誤。
• 無論如何，互動庫將在執行完該函式後，輸出相應資訊並立即終止執行。

你應當保證呼叫 query 或 check 函式時傳入的參數符合上述要求。

你可以查看下發檔案中的參考互動庫了解更多實作細節。

測試程式方式

下發檔案中提供了互動庫的參考實作 grader.cpp。最終測試時所用的互動庫實作與該實作有不同，因此選手的解法不應依賴互動庫實作。

假設你的原始程式名為 puzzle.cpp，你需要將下發檔案放入原始程式所在的目錄中，並在目錄下使用如下指令編譯得到可執行程式：

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

執行按上述方法編譯得到的可執行檔案時：

• 可執行檔案將從標準輸入讀入以下格式的資料：

  • 第一行：一個正整數 $n$，表示排列長度。你需要保證 $2 \leq n \leq 1000$；
  • 第二行：$n$ 個整數 $p_0,p_1,\cdots,p_{n-1}$，表示答案排列。你需要保證 $p_0,\cdots,p_{n-1}$ 是一個長度為 $n$ 的排列，即 $0 \sim n-1$ 中的所有整數均恰好出現一次。

• 讀入完成之後，互動庫將用該組資料進行測試，並輸出如下內容：

  • 如果你的程式正常執行，呼叫 query 函式的次數不超過 $20000$，並在呼叫 check 函式時傳入了正確的排列，則會輸出以下內容：

    Correct.
    cnt = x

    其中 $x$ 為你的程式呼叫 query 函式的次數。

  • 否則，將會輸出相應的錯誤資訊。

範例

輸入 1

3
1 0 2

輸出 1

Correct.
cnt = 3

說明 1

這是使用下發的 grader.cpp 和能夠正確執行的原始程式得到的可能輸出檔案。

對於此範例，一種可能的呼叫方式為：

• 呼叫 query([0, 1, 2])，返回 $1$；
• 呼叫 query([0, 2, 1])，返回 $0$；
• 呼叫 query([1, 0, 2])，返回 $3$；
• 呼叫 check([1, 0, 2])。

評分方式

評測時，你只需在 OJ 上提交你的原始程式，修改下發的其他檔案不會對評測結果產生影響。

本題首先會受到和傳統題相同的限制，例如編譯錯誤會導致整道題目得 $0$ 分，執行時錯誤、超過時間限制、超過空間限制等會導致相應測試點得 $0$ 分等。你只能存取自己定義的和互動庫給出的變數及其對應的記憶體空間，嘗試存取其他空間將可能導致編譯錯誤或執行錯誤。

在上述條件以外，在一個測試點中，若你的程式執行了非法的函式呼叫、沒有呼叫 check 函式或 check 函式給出了錯誤回答、或呼叫 query 函式的次數超過 $20000$，該測試點將會獲得 $0$ 分。否則，該測試點的得分將由下述「子任務」中的描述給出。

子任務

本題使用捆綁測試。對於每個子任務而言，你的得分是子任務中所有測試點得分的最小值。

對於所有測試點，$1 \leq n \leq 1000$。

對於前 $6$ 個子任務，如果你的程式正常執行，呼叫 query 函式的次數不超過 $20000$，並在呼叫 check 函式時傳入了正確的排列，則可以獲得該測試點的滿分。

對於第 $7$ 個子任務，你的程式在上述基礎之上還可能獲得部分分。設你的程式呼叫 query 的次數為 $m$，則你的得分如下：

說明

保證對於任何合法的資料及在限制範圍內的呼叫，互動庫本身執行所用的時間不會超過 $\mathrm{0.2s}$，執行所用的空間不會超過 $\mathrm{128MiB}$。

互動庫正常執行需包含的標頭檔已經在下發的參考互動庫中給出，你的程式可以包含你需要的標頭檔。

本題的互動庫不是自適應的，即在 play 函式呼叫之前答案排列就已經確定，不會根據你的詢問而變化。

透過存取輸入輸出檔案、攻擊評測系統或攻擊評測庫等方式得分屬於作弊行為，所得分數無效。