链接: https://cses.fi/problemset/task/3140

板块: Interactive Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有一个隐藏的排列 $a_1, a_2,\dots, a_n$，由整数 $1, 2,\dots, n$ 组成。你的任务是通过翻转子数组来将这个排列排序。

在每一回合，你可以翻转排列的一个子数组。之后，评测机会告诉你该排列的逆序对数量。如果逆序对数量为 $0$（即排列已排好序），你就获胜。

输入

这是一个交互题。你的程序将通过标准输入和输出与评测机进行交互。你应当先读取一个整数 $n$：排列的长度。

在你的回合中，输出两个整数 $i$ 和 $j$：翻转下标 $i$ 和 $j$ 之间的子数组。

此后，下一行输入会包含一个整数：操作之后排列的逆序对数量。如果该数量为 $0$，你即获胜，且你的程序必须在输出此行后终止。

输出

参见上述交互协议。

数据范围

$1 \leq n \leq 1000$ 你最多可以进行 $4n$ 次操作

样例

3
1 2
1
2 3
0

说明：此处初始排列为 $[3,1,2]$。第一次操作后排列变为 $[1,3,2]$，逆序对数量为 $1$。第二次操作后排列变为 $[1,2,3]$，逆序对数量为 $0$。