在 2016 年佳媛姐姐喜欢上叻数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题现在她在研究一个难题，需要你来帮助她

这个难题是这样子的：给出一個 1 到 n 的排列，现在对这个排列序列进行 m 次局部排序排序分为两种：

注意，这里是对下标在区间 [l,r] 内的数排序
最后询问第 q 位置上的数字。

输入数据的第一行为两个整数 n 和 mn 表示序列的长度，m 表示局部排序的次数

第二行为 n 个整数，表示 1 到 n 的一个排列

最后输入一个整数 q，表示排序完之后询问的位置

输出数据仅有一行，一个整数表示按照顺序将全部的部分排序结束后第 q 位置上的数字。

河北省选2016第一天第二题

最简单的做法是每次都排序，但复杂度上显然不能够通过

考虑优化一下这个做法。首先发现答案具有单调性那么就二分一个mid，把大于等于mid的数变为1小于mid的数变成0。排序时如果是顺序排序，就可以把所有0放在区间前面1放在区间后面；逆序同理。这可以用线段树实现如果最后第q为上是1，说明还可以有更大的mid否则说明当前的mid过大。