לאחר כמה מאות שנים, העיר JOI הפכה לעיר חרבה. החוקרת IOI-chan חוקרת כעת את האזור שבו נבנתה הספרייה. מתוצאות החקירה ידועים הדברים הבאים:

• בספרייה של העיר JOI הייתה כוננית אופקית. היו בה $N$ מקומות בשורה להנחת ספרים, ממוספרים מ־$0$ עד $N-1$ משמאל לימין. בכל מקום היה אפשר להניח בדיוק ספר אחד.
• בכוננית היו $N$ ספרים. הספרים היו ממוספרים מ־$0$ עד $N-1$.
• סידור הספרים הוא דרך להניח את כל $N$ הספרים ב־$N$ המקומות.
• היה סידור נכון של הספרים, ובו הספר $B_i$ ($0 \le i \le N-1$) הונח במקום $i$. כל ערכי $B_i$ שונים זה מזה.

סידור הספרים משתנה לעיתים קרובות. ידוע שבספרייה זו החזירו את הספרים לסידור הנכון באמצעות חזרה על הפעולה הבאה.

פעולה: יהי הספר $x$ הספר השמאלי ביותר מבין הספרים שמקומם שונה ממקומם בסידור הנכון. יהי הספר $y$ הספר שנמצא בסידור הנוכחי במקום שבו הספר $x$ נמצא בסידור הנכון. החליפו את מקומם של הספר $x$ והספר $y$.

אף ש־IOI-chan מצאה את ספריה הישנים של הספרייה, היא לא הצליחה לדעת מהו הסידור הנכון. אולם היא מצאה מכונה ישנה שניהלה את פעולות הכוננית. אם מציינים סידור של $N$ הספרים ושולחים שאילתה למכונה, היא משיבה כמה פעולות נדרשות כדי להחזיר את כל הספרים לסידור הנכון. IOI-chan רוצה לגלות את הסידור הנכון באמצעות שאילתות למכונה. מכיוון שהמכונה ישנה, אפשר לשלוח אליה לכל היותר $5\,000$ שאילתות.

כתבו תוכנית שבהינתן המידע על הכוננית, מזהה את הסידור הנכון של הספרים באמצעות לכל היותר $5\,000$ שאילתות.

פרטי מימוש

עליכם להגיש קובץ אחד.

הקובץ הוא library3.cpp. עליו לממש את הפונקציה הבאה. על התוכנית לכלול את library3.h באמצעות הוראת קדם־המעבד #include.

void solve(int N)

פונקציה זו נקראת פעם אחת בלבד לכל מקרה בדיקה.

• הפרמטר $N$ הוא מספר הספרים $N$.

בתוך library3.cpp, אפשר לקרוא לפונקציות הבאות.

int query(const std::vector<int> a)

באמצעות פונקציה זו, IOI-chan שולחת שאילתה למכונה.

• הפרמטר $a$ הוא מערך באורך $N$ המציין את סידור $N$ הספרים שיש לציין בשאילתה. משמעותו היא שבסידור שצוין, הספר a[i] ($0 \le i \le N-1$) מונח במקום $i$.
• הערך המוחזר הוא מספר הפעולות הנדרשות להחזרת כל הספרים לסידור הנכון, החל מהסידור שצוין.
• אורך הפרמטר $a$ חייב להיות $N$. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [1].
• כל איבר בפרמטר $a$ חייב להיות בין $0$ ל־$N-1$. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [2].
• כל איבר בפרמטר $a$ חייב להיות שונה מכל האחרים. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [3].
• אסור לקרוא לפונקציה query יותר מ־$5\,000$ פעמים. אם היא נקראת יותר מ־$5\,000$ פעמים, התוכנית תישפט כ־Wrong Answer [4].

void answer(std::vector<int> b)

התוכנית עונה מהו הסידור הנכון של הספרים באמצעות קריאה לפונקציה זו.

• הפרמטר $b$ הוא מערך באורך $N$ המציין את סידור $N$ הספרים שיש לציין בתשובה. משמעותו היא שבסידור שבתשובה, הספר b[i] ($0 \le i \le N-1$) מונח במקום $i$.
• אורך הפרמטר $b$ חייב להיות $N$. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [5].
• כל איבר בפרמטר $b$ חייב להיות בין $0$ ל־$N-1$. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [6].
• כל איבר בפרמטר $b$ חייב להיות שונה מכל האחרים. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [7].
• הסידור שנמסר בתשובה חייב להיות הסידור הנכון. אם תנאי זה אינו מתקיים, התוכנית תישפט כ־Wrong Answer [8].
• יש לקרוא לפונקציה answer בדיוק פעם אחת. אם היא נקראת יותר מפעם אחת, התוכנית תישפט כ־Wrong Answer [9]. כאשר הפונקציה solve מסתיימת, אם הפונקציה answer לא נקראה, התוכנית תישפט כ־Wrong Answer [10].

הערות חשובות

• התוכנית יכולה לממש פונקציות נוספות לשימוש פנימי או להשתמש במשתנים גלובליים.
• אסור לתוכנית להשתמש בקלט הסטנדרטי ובפלט הסטנדרטי. אסור לתוכנית לתקשר עם קבצים אחרים בשום דרך. עם זאת, מותר לתוכנית להדפיס מידע לניפוי שגיאות לפלט השגיאות הסטנדרטי.

הידור והרצת בדיקה

אפשר להוריד מאתר התחרות קובץ ארכיון המכיל תוכנית בדיקה לדוגמה כדי לבדוק את התוכנית שלכם. הארכיון מכיל גם קובץ קוד מקור לדוגמה לתוכנית שלכם.

תוכנית הבדיקה לדוגמה היא הקובץ grader.cpp. כדי לבדוק את התוכנית, שימו את grader.cpp, library3.cpp ו־library3.h באותה תיקייה והריצו את הפקודה הבאה להידור התוכניות. לחלופין, אפשר להריץ את compile.sh הכלול בארכיון.

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

כאשר ההידור מצליח, נוצר קובץ ההרצה grader.

שימו לב שתוכנית הבדיקה האמיתית שונה מתוכנית הבדיקה לדוגמה. תוכנית הבדיקה לדוגמה תרוץ כתהליך יחיד, שיקרא נתוני קלט מהקלט הסטנדרטי ויכתוב את התוצאות לפלט הסטנדרטי.

הקלט של תוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה קוראת את הנתונים הבאים מהקלט הסטנדרטי.

N
B_0 B_1 ... B_{N-1}

$B_i$ ($0 \le i \le N-1$) הוא מספר הספר המונח במקום $i$ בסידור הנכון.

הפלט של תוכנית הבדיקה לדוגמה

תוכנית הבדיקה לדוגמה מדפיסה את המידע הבא לפלט הסטנדרטי ולפלט השגיאות הסטנדרטי (המירכאות נועדו להבהרה).

• אם התוכנית נשפטת כנכונה, היא מדווחת את מספר הקריאות ל־query בצורה כגון Accepted: 3000.
• אם התוכנית נשפטת כסוג כלשהו של Wrong Answer, תוכנית הבדיקה לדוגמה כותבת את סוגו בצורה כגון Wrong Answer [3].

אם התוכנית מקיימת תנאים של כמה סוגי Wrong Answer, תוכנית הבדיקה לדוגמה מדווחת רק על אחד מהם.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $2 \le N \le 500$.
• $0 \le B_i \le N-1$ ($0 \le i \le N-1$).
• $B_i \ne B_j$ ($0 \le i<j \le N-1$).
• כל הערכים הנתונים הם מספרים שלמים.

תת־משימות

1. (2 נקודות) $N \le 6$.
2. (19 נקודות) $N \le 100$.
3. (79 נקודות) אין מגבלות נוספות.

תקשורת לדוגמה

להלן קלט לדוגמה לתוכנית הבדיקה לדוגמה וקריאות הפונקציה המתאימות.

קלט 1

4
2 0 3 1

קריאות פונקציה לדוגמה

לדוגמה, הקריאה query([0, 1, 2, 3]) מציינת סידור שבו הספרים $0,1,2,3$ מונחים במקומות $0,1,2,3$ בהתאמה. הפעולה תחזור על עצמה כך:

1. מחליפים את מקומם של הספר $0$ והספר $1$. במקומות $0,1,2,3$ מונחים הספרים $1,0,2,3$ בהתאמה.
2. מחליפים את מקומם של הספר $1$ והספר $3$. במקומות $0,1,2,3$ מונחים הספרים $3,0,2,1$ בהתאמה.
3. מחליפים את מקומם של הספר $3$ והספר $2$. במקומות $0,1,2,3$ מונחים הספרים $2,0,3,1$ בהתאמה.

מכיוון שמספר הפעולות הנדרשות להחזרת כל הספרים לסידור הנכון הוא $3$, הערך המוחזר הוא $3$.

קלט לדוגמה זה מקיים את המגבלות של כל תת־המשימות.