CF1498E.Two Houses

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

There is a city in which Dixit lives. In the city, there are $n$ houses. There is exactly one directed road between every pair of houses. For example, consider two houses A and B, then there is a directed road either from A to B or from B to A but not both. The number of roads leading to the $i$-th house is $k_i$.

Two houses A and B are bi-reachable if A is reachable from B and B is reachable from A. We say that house B is reachable from house A when there is a path from house A to house B.

Dixit wants to buy two houses in the city, that is, one for living and one for studying. Of course, he would like to travel from one house to another. So, he wants to find a pair of bi-reachable houses A and B. Among all such pairs, he wants to choose one with the maximum value of $|k_A - k_B|$, where $k_i$ is the number of roads leading to the house $i$. If more than one optimal pair exists, any of them is suitable.

Since Dixit is busy preparing CodeCraft, can you help him find the desired pair of houses, or tell him that no such houses exist?

In the problem input, you are not given the direction of each road. You are given — for each house — only the number of incoming roads to that house ($k_i$).

You are allowed to ask only one type of query from the judge: give two houses A and B, and the judge answers whether B is reachable from A. There is no upper limit on the number of queries. But, you cannot ask more queries after the judge answers "Yes" to any of your queries. Also, you cannot ask the same query twice.

Once you have exhausted all your queries (or the judge responds "Yes" to any of your queries), your program must output its guess for the two houses and quit.

See the Interaction section below for more details.

这是一个交互式问题。在与评测程序通信时，请务必刷新你的输出。你可以在 C++ 中使用 fflush(stdout)，Java 中使用 system.out.flush()，Python 中使用 stdout.flush()，Pascal 中使用 flush(output) 来刷新输出。如果你使用其他编程语言，请查阅其文档。你也可以参考交互式问题指南：https://codeforces.com/blog/entry/45307。

迪克西特居住在一座城市中。该城市共有 $n$ 座房屋。任意两座房屋之间恰好存在一条有向道路。例如，考虑两座房屋 A 和 B，则要么存在一条从 A 到 B 的有向道路，要么存在一条从 B 到 A 的有向道路，但不会同时存在两条。第 $i$ 座房屋的入度（即指向它的道路数量）为 $k_i$。

若房屋 A 可从 B 到达，且 B 也可从 A 到达，则称 A 和 B 是双向可达的（bi-reachable）。我们称房屋 B 可从房屋 A 到达，当且仅当存在一条从 A 到 B 的路径。

迪克西特想在该城市购买两座房屋——一座用于居住，另一座用于学习。显然，他希望能在两座房屋之间往返通行。因此，他希望找到一对双向可达的房屋 A 和 B。在所有这样的房屋对中，他希望选择使 $|k_A - k_B|$ 最大的那一对，其中 $k_i$ 表示第 $i$ 座房屋的入度。若存在多个最优对，输出任意一个即可。

由于迪克西特正忙于准备 CodeCraft 比赛，你能帮他找出这样一对房屋，或者告诉他这样的房屋对根本不存在吗？

在本题输入中，你不会被直接给出每条道路的方向。你仅会被告知——对每一座房屋 $i$——其入度 $k_i$。

你只允许向评测系统提出一种类型的查询：给出两座房屋 A 和 B，评测系统将回答“B 是否可从 A 到达”。查询次数没有上限。但一旦评测系统对你的某次查询返回 “Yes”，你就不能再进行任何后续查询。此外，你不能重复询问同一对 (A, B)。

当你用尽所有查询机会（或评测系统对某次查询返回 “Yes”）后，你的程序必须立即输出所猜测的两座房屋并退出。

更多细节请参见下方的“交互方式（Interaction）”部分。

The first line contains a single integer $n$ ($3 \le n \le 500$) denoting the number of houses in the city. The next line contains $n$ space-separated integers $k_1, k_2, \dots, k_n$ ($0 \le k_i \le n - 1$), the $i$-th of them represents the number of incoming roads to the $i$-th house.

第一行包含一个整数 $n$（$3 \le n \le 500$），表示城市中房屋的数量。
第二行包含 $n$ 个用空格分隔的整数 $k_1, k_2, \dots, k_n$（$0 \le k_i \le n - 1$），其中第 $i$ 个数表示第 $i$ 栋房屋的入度（即指向该房屋的道路数量）。

In the first sample input, we are given a city of three houses with one incoming road each. The user program asks one query: "? 1 2": asking whether we can reach from house $1$ to house $2$. The judge responds with "Yes". The user program now concludes that this is sufficient information to determine the correct answer. So, it outputs "! 1 2" and quits.

In the second sample input, the user program queries for six different pairs of houses, and finally answers "! 0 0" as it is convinced that no two houses as desired in the question exist in this city.

在第一个样例输入中，我们得到一座包含三栋房屋的城市，每栋房屋恰好有一条入边。用户程序提出一个查询：“? 1 2”：询问是否能从房屋 $1$ 到达房屋 $2$。评测程序回应“Yes”。此时，用户程序认为该信息已足以确定正确答案，于是输出“! 1 2”并退出。

在第二个样例输入中，用户程序对六对不同的房屋进行了查询，最终输出“! 0 0”，因为它确信该城市中不存在题目所要求的任意两栋房屋。