ヒント → https://atcoder.jp/contests/arc192/editorial/12151

複数の方針があると思いますが、ここではWriterの方針を紹介します。以下の解法は、\(A\) の要素がすべて正でないと破綻することに注意してください。

まず、すぬけくんに \((1,2),(1,3),\dots,(1,N)\) とクエリを送ります。このうち返り値が最も大きいクエリを \((1,m)\) とします。このとき、\(P_m=1\) または \(P_m=N\) が成り立ちます。ここでは、\(P_m=1\) と仮定します。

その後、\((m,1),(m,2),\dots,(m,N)\) のうち \((m,m)\) 以外のクエリを送ります。これらを返り値の昇順に並べたものを \((m,x_1),(m,x_2),\dots,(m,x_{N-1})\) とすると、\(P_{x_1}=2,P_{x_2}=3,\dots,P_{x_{N-1}}=N\) が成り立ちます。

また、\((m,x_i)\) の返り値から \((m,x_{i-1})\) の返り値を引いたものは \(A_{i+1}\) の値に等しいです。よって、\(A_3,A_4,\dots,A_N\) は特定できます。

\((m,x_{N-1})\) とクエリを送っていることより、現時点で \(A\) の総和を知っています。\(A_1\) を知ることさえできれば、\(A_2\) も求まってこの問題を解くことができます。

これは \((x_1,x_{N-1})\) とクエリを送ることでわかります。このクエリの返り値は \(A\) の総和から \(A_1\) を引いたものであるためです。

ところで、ここまで \(P_1\lt P_2\) という制約を考えていませんでした。この制約に違反する場合、\(P_m=1\) と仮定したのが間違いであるため、\(P_m=N\) として配列を作り直せばよいです。これは以下のようにすることで実現できます。

• \(1\leq i\leq N\) なるすべての整数 \(i\) について、\(P_i\) を \(N+1-P_i\) で置き換える。
• \(A\) を反転する。

このように作り直したとき、クエリの返り値が一切変わらないことがわかります。また、\(P_1\gt P_2\) ならば \(N+1-P_1\lt N+1-P_2\) であるため、制約違反も回避することができます。

クエリの回数を見積もると高々 \(2N-1\) 回で、制約を満たしています。

実装例 (PyPy3)

def query(s, t):
    print("?", s + 1, t + 1)
    ret = int(input())
    assert ret != -1
    return ret


N = int(input())
mx = (-1, -1)

for i in range(1, N):
    mx = max(mx, (query(0, i), i))

P = [0] * N
A = [0] * N
P[mx[1]] = 1
resps = []

for i in range(N):
    if mx[1] != i:
        resps.append((query(mx[1], i), i))

resps.sort()

for i in range(N - 1):
    P[resps[i][1]] = i + 2
    if 1 <= i:
        A[i + 1] = resps[i][0] - resps[i - 1][0]

A[0] = resps[-1][0] - query(resps[0][1], resps[-1][1])
A[1] = resps[-1][0] - sum(A)

if P[0] > P[1]:
    P = [N + 1 - p for p in P]
    A = A[::-1]

print("!", *P, *A)