AT_kupc2020_j

考虑 $n=4$ 怎么做。

对 $(1,2,3),(1,2,4),(1,3,4),(2,3,4)$ 分别进行询问，可以发现一定能得到两个不同的中位数 $L,R$，令 $L<R$，则有一定有两组询问回答为 $L$，两组为 $R$。

然后你可以发现对于 $i$，在所有包含 $i$ 的询问的回答只能是两种情况：两个 $L$ 和一个 $R$，两个 $R$ 和一个 $L$，如果出现两个 $L$ 则有 $a_i\le L$，反之如果出现两个 $R$ 则有 $a_i\ge R$。证明可以把所有情况列出来（）

显然存在排列 $p$ 满足 $a_{p_1}<L,a_{p_2}=L,a_{p_3}=R,a_{p_4}>R$。不妨令满足 $a_i\le L$ 的两个 $i$ 为 $l_1,l_2$，满足 $a_i\ge R$ 的两个 $i$ 为 $r_1,r_2$，根据前面的结论我们可以通过这些询问找出 $l_1,l_2,r_1,r_2$。

然后你发现 $l_1$ 和 $l_2$ 是无法通过询问 $1$ 区分的，$r_1$ 和 $r_2$ 同理，那么就用两次询问 $2$ 区分即可。

考虑 $n>4$。

同样的，我们可以通过询问 $1$ 知道 $l_1,l_2,r_1,r_2$ 和 $L,R$。

对于 $i$，进行询问 $(l_1,r_1,i)$，令回答为 $s$，如果 $L<s<R$ 则说明 $a_i=s$。

如果 $s\le L$，则再进行询问 $(l_2,r_2,i)$，令回答为 $t$，如果 $s<t$，有 $a_{l_1}\le s<t=a_{l_2}$，根据前面的结论 $a_{l_2}=L$。否则有 $a_{l_2}\le t<s=a_{l_1}$，有 $a_{l_1}=L$。

$s\ge R$ 同理。

假设 $s<t,s\le L$，现在可以发现我们无法通过询问 $1$ 知道 $a_{l_1}$ 和 $a_i$，但是知道 $\max(a_{l_1},a_i)=s$，然后可以发现 $a_{l_1},a_i,a_{r_1}$ 的中位数和 $a_{l_1},a_i,a_{r_1}$ 的中位数为 $s$，这又是前面的形式，令 $L\gets s$ 即可。

$s>t$ 的情况和 $s\ge R$ 的情况同理。

最后你发现还有 $l_1,l_2,r_1,r_2$ 未确定，这个时候就用两次询问 $2$ 确定。