레이팅 미적용The first semester at the university is coming to an end. Marin decided to attend
a PE class in order to collect his 12th attendance and thus pass the course. He
was surprised by the number of students waiting in front of the gym.
He counted \(n\) students (including himself) and noticed an interesting property:
no two students have the same height, and for every integer from 1 to \(n\) there is
exactly one student of that height.
Before the class started, the students lined up in a row. The heights of the students
in the row, observed from left to right, form a permutation \(p\) of size \(n\). The
professor has some unusual requirements for the order of students in the row, so
he decided to issue \(q\) commands that must be executed in the given order.
Each command is of the form \(l_{i}\) \(r_{i}\) and means that the students at positions from \(l_{i}\) to \(r_{i}\) (inclusive) need
to step out of the row, and then fill the empty positions in the following way: position \(l_{i}\) is filled by the
shortest student among those taken out. Position \(l_{i} + 1\) is filled by the tallest of the remaining students.
Position \(l_{i} + 2\) is again filled by the shortest of the remaining students, position \(l_{i} + 3\) by the tallest, and
so on, alternating between the shortest and the tallest until position \(r_{i}\) is filled.
After executing all the commands, Marin is no longer sure whether he is standing in the correct position
or if at some point he moved to the wrong place. However, he remembers the initial permutation \(p\), all \(q\)
commands in the order they were given, and he has told you his height \(m\). He asks you to determine the
position where he should be standing.
The first line contains three natural numbers \(n\), \(q\) i \(m\) (\(1 \le n\), \(q \le 10^{5}\), \(1 \le m \le n\)), the numbers from the
problem statement.
The second line contains a sequence of \(n\) numbers \(1 \le p_{i} \le n\), the permutation \(p\).
Each of the next \(q\) lines contain two numbers \(1 \le l_{i} \le r_{i} \le n\), the \(i\)-th command.
In the first and only line output one number - the position Marin should occupy.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 7점 | n, \(q \le 1000\) |
2 | 11점 | \(l_{i} = 1\), for each \(1 \le i \le q\) |
3 | 17점 | \(m = 1\) or \(m = n\) |
4 | 24점 | n, \(q \le 5000\) |
5 | 51점 | No additional constraints. |
7 3 3
4 2 3 7 1 6 5
4 7
3 5
1 456 4 1
5 3 6 2 1 4
2 4
3 5
2 6
5 628 2 5
8 7 6 5 4 3 1 2
2 8
1 77Explanation of the first sample test: After executing the first command, the heights of the students
in the row are: 4 2 3 1 7 5 6. After executing the second command the heights are: 4 2 1 7 3 5 6. In the
end, after executing the third command, the row should look like this: 1 7 2 4 3 5 6. Marin should occupy
the 5th position from the left.