Hints: https://atcoder.jp/contests/arc192/editorial/12197

There are several approaches; here we describe the method preferred by the writer. Note that the following solution will fail if any element of \(A\) is not positive.

First, send queries to Snuke for the pairs \((1,2),(1,3),\dots,(1,N)\). Among these, let \((1,m)\) be the query with the largest returned value. Then, we have either \(P_m=1\) or \(P_m=N\). In what follows we assume \(P_m=1\).

Next, send queries for all pairs \((m,1), (m,2), \dots, (m,N)\), except for \((m,m)\). Sort these queries in increasing order of the returned values; denote them as \((m,x_1),(m,x_2),\dots,(m,x_{N-1})\). Then, it holds that \(P_{x_1}=2,P_{x_2}=3,\dots,P_{x_{N-1}}=N\).

Moreover, the difference between the returned value for \((m,x_i)\) and that for \((m,x_{i-1})\) is equal to \(A_{i+1}\). Hence, \(A_3,A_4,\dots,A_N\) can be determined.

Since we have sent a query for \((m,x_{N-1})\), at this point we know the sum of \(A\). Once \(A_1\) is determined, \(A_2\) can also be computed.

This can be done by sending a query for \((x_1,x_{N-1})\). The returned value for this query is equal to the sum of \(A\) minus \(A_1\).

Up to this point we have not considered the constraint \(P_1<P_2\). If this constraint is violated, then the assumption \(P_m=1\) was incorrect; in that case, redefine the array with \(P_m=N\), as follows:

• For every \(1\leq i\leq N\), replace \(P_i\) with \(N+1-P_i\).
• Reverse \(A\).

This transformation does not change any query results, and since if \(P_1>P_2\) then \(N+1-P_1<N+1-P_2\), the constraint is satisfied.

The total number of queries used is at most \(2N-1\), which satisfies the constraints.

Sample Implementation (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)