#!/usr/bin/env python3
#
# Testing tool for the Historical Hierarchy problem
#
# Usage:
#
#   python3 testing_tool.py -f inputfile <program invocation>
#
#
# Use the -f parameter to specify the input file, e.g. 1.in.
# The input file should contain two lines:
# - The first line contains one integer `n`, the number of historic events you need to order.
# - The second line contains `n` integers, the hidden permutation of values from 1 to `n` that needs to be ordered.

# You can compile and run your solution as follows:

# C++:
#   g++ solution.cpp
#   python3 testing_tool.py -f 1.in ./a.out

# Python:
#   python3 testing_tool.py -f 1.in python3 ./solution.py

# Java:
#   javac solution.java
#   python3 testing_tool.py -f 1.in java solution

# Kotlin:
#   kotlinc solution.kt
#   python3 testing_tool.py -f 1.in kotlin solutionKt


# The tool is provided as-is, and you should feel free to make
# whatever alterations or augmentations you like to it.
#
# The tool attempts to detect and report common errors, but it is not an exhaustive test.
# It is not guaranteed that a program that passes this testing tool will be accepted.


import argparse
import subprocess
import traceback

parser = argparse.ArgumentParser(description="Testing tool for problem Historical Hierarchy.")
parser.add_argument(
    "-f",
    dest="inputfile",
    metavar="inputfile",
    default=None,
    type=argparse.FileType("r"),
    required=True,
    help="The input file to use.",
)
parser.add_argument("program", nargs="+", help="Invocation of your solution")

args = parser.parse_args()

with (
    args.inputfile as f,
    subprocess.Popen(
        " ".join(args.program),
        shell=True,
        stdout=subprocess.PIPE,
        stdin=subprocess.PIPE,
        universal_newlines=True,
    ) as p,
):
    assert p.stdin is not None and p.stdout is not None
    p_in = p.stdin
    p_out = p.stdout

    def write(line: str):
        assert p.poll() is None, "Program terminated early"
        print(f"Write: {line}", flush=True)
        p_in.write(f"{line}\n")
        p_in.flush()

    def read() -> str:
        line = p_out.readline().strip()
        if line == "":
            assert p.poll() is None, "Program terminated early"
        assert line != "", "Read empty line or closed output pipe"
        print(f"Read: {line}", flush=True)
        return line

    # Parse input
    lines = f.readlines()
    n = int(lines[0])
    perm = list(map(int, lines[1].split()))
    assert sorted(perm) == [*range(1, n + 1)], "second line of input should be a permutation of 1 to n"
    QUERY_LIMIT = n * n * 4

    # Simulate interaction
    try:
        write(f"{n}")
        queries = 0

        while True:
            queries += 1
            i, j = map(int, read().split())
            assert queries <= QUERY_LIMIT, "Number of queries should not exceed 4*n^2"
            assert 1 <= i <= n, "i not in bounds"
            assert 1 <= j <= n, "j not in bounds"
            i -= 1
            j -= 1  # convert to 0-based indexing
            x = perm[i]
            perm.remove(x)
            perm.insert(j, x)

            # Calculate the LIS
            dp = [0] * n
            for i1 in range(n):
                dp[i1] += 1
                for j1 in range(i1 + 1, n):
                    if perm[i1] < perm[j1]:
                        dp[j1] = max(dp[j1], dp[i1])
            lis = max(dp)

            write(f"{lis}")
            if lis == n:
                break

        print("You sorted the historic events")
        print(f"Queries used: {queries}", flush=True)
        extra = p_out.readline()
        assert extra == "", (
            f"Your submission printed extra data after finding a solution: '{extra[:100].strip()}{'...' if len(extra) > 100 else ''}'"
        )
        print(f"Exit code: {p.wait()}", flush=True)
        assert p.wait() == 0, "Your submission did not exit cleanly after finishing"

    except AssertionError as e:
        print()
        print(f"Error: {e}")
        print()
        print("Killing your submission.", flush=True)
        p.kill()
        exit(1)

    except Exception:
        print()
        print("Unexpected error:")
        traceback.print_exc()
        print()
        print("Killing your submission.", flush=True)
        p.kill()
        exit(1)