这道题目很像分治，如果将下标序列\([1,n]\)以\(a_i\)为关键字排序，排序之后的逆序列就是答案
我们学过的有关分治的排序方法：快速排序和归并排序。这里使用快速排序
这里看官方解答就好了，写的挺清楚的
然后官方解答还给了一个非随机算法，具体来说，就是先从左到右询问每个位置，如果是<，就一直询问直到=；否则的话就询问下一个位置（在询问下一个位置之前，利用上一次=的位置将\(x\)复原）。
这样的话，最后一次<的位置就是\(1\)，因为当询问到\(1\)的时候，\(x\)无论为多少，都会<直到=，然后\(x\)就会变成\(1\)，之后都是>；由于每次都要复原，所以就能确定\(1\)的位置；同理可以找出\(n\)的位置
然后我们就可以将\(x\)调整为\(\frac{n}{2}\)，然后利用随机化算法类似的过程进行快速排序就好了（此时递归次数就是确定的）
标签：Task,分治,算法,排序,Order,ace5 From： https://www.cnblogs.com/dingxingdi/p/18024560