Finding Array Tutorial

원본 수열 $A$에서 $A_i$가 고유한 원소이기 위해서는 부분 배열 $[A_1, A_2, \cdots, A_{i-1}]$과 $[A_{i+1}, \cdots, A_{N-1}, A_N]$에 $A_i$와 같은 값이 존재하지 않아야 합니다.

배열 $p_i$에 "$? \ 1 \ i$" 질문에 대한 답을 저장해 둡시다.

배열 $s_i$에 "$? \ i \ N$" 질문에 대한 답을 저장해 둡시다.

$A_i$가 고유한 원소이기 위한 필요충분조건은 $p_i = p_{i-1}+1$과 $s_i = s_{i+1}+1$을 동시에 만족하는 것입니다.

따라서 총 $2N$개의 질문으로 문제를 해결할 수 있습니다.