Imprecise Permutation Sort

This is an interactive problem.

A permutation $a\[1], a\[2], \ldots, a\[n]$ of integers from $1$ to $n$ is hidden from you.

Your task is to sort it in ascending order by comparing and swapping pairs of elements. This problem could be pretty easy, but the jury member responsible for the problem was too concentrated on floating-point arithmetic in problems G and J and implemented an "imprecise" comparator:

• if $\frac{|a\[i] - a\[j]|}{max(a\[i], a\[j])} \leq 0.01$, then return $0$;
• otherwise, if $a\[i] < a\[j]$, then return $-1$;
• otherwise, return $1$.

Your program can make queries to compare any two elements with this comparator, or to swap any two elements. After each swap, it will be told whether the permutation became sorted. 

Sort a permutation of size up to $16\\,384$ using no more than $300\\,000$ queries.