公式解説とは別の方針です．

\((1,k),(2,k)\) の形のクエリを全て尋ねてみることを考えます． \((1,1),(2,2)\) は尋ねることができず，\((1,2),(2,1)\) は同じ値が返されることに注意するとクエリ回数を \(2N-3\) 回消費することになります．

クエリ \((1,k),(2,k)\) の答えをそれぞれ \(X_k,Y_k\) とします（\(X_1,Y_2\) は未定義）． このとき制約より \(3\leq k\leq N\) に対し以下が成り立ちます．

• \(X_k\leq X_2\) かつ \(Y_k\leq Y_1\) ならば \(P_1<P_k<P_2\)
• そうでなく \(X_k>Y_k\) ならば \(P_k<P_1\)
• それ以外ならば \(P_2<P_k\)

上の条件に従って \(k\) を \(3\) つに分け，各グループ内で \(X_k\) の大小を比較することで \(P\) が特定できます．

\(x\neq P_1,P_2\) に対する \(A_x\) の値は新たなクエリを尋ねることなく計算できます．また \(A_{P_1},A_{P_2}\) についてもクエリが \(3\) 回分残っているので，直接尋ねることはできないものの容易に求められます．

実装例(PyPy3)