Học kỳ đầu tiên ở trường đại học sắp kết thúc. Marin quyết định tham gia một buổi học thể dục để điểm danh lần thứ ~12~ và đủ điều kiện qua môn. Cậu khá bất ngờ vì số lượng sinh viên đang đứng chờ trước nhà thi đấu.

Marin đếm được ~n~ sinh viên, kể cả bản thân mình, và nhận ra một tính chất thú vị: không có hai sinh viên nào có cùng chiều cao, và với mỗi số nguyên từ ~1~ tới ~n~ thì có đúng một sinh viên mang chiều cao đó.

Trước khi buổi học bắt đầu, các sinh viên đứng thành một hàng. Dãy chiều cao khi quan sát từ trái sang phải tạo thành một hoán vị ~p~ có độ dài ~n~. Giáo viên có một số yêu cầu khá lạ về thứ tự trong hàng, nên ông đưa ra ~q~ lệnh và các lệnh này phải được thực hiện đúng theo thứ tự đã cho.

Mỗi lệnh có dạng ~l_i~ ~r_i~, nghĩa là các sinh viên ở các vị trí từ ~l_i~ đến ~r_i~ (tính cả hai đầu) phải bước ra khỏi hàng, rồi quay lại lấp chỗ trống như sau:

• vị trí ~l_i~ được điền bởi người thấp nhất trong nhóm vừa bước ra,
• vị trí ~l_i + 1~ được điền bởi người cao nhất trong số còn lại,
• vị trí ~l_i + 2~ lại được điền bởi người thấp nhất trong số còn lại,
• vị trí ~l_i + 3~ lại được điền bởi người cao nhất trong số còn lại,

và cứ tiếp tục xen kẽ như vậy cho tới khi lấp xong vị trí ~r_i~.

Sau khi thực hiện xong tất cả các lệnh, Marin không còn chắc mình đang đứng đúng vị trí hay đã bị lệch chỗ ở một thời điểm nào đó. Tuy nhiên, cậu vẫn nhớ hoán vị ban đầu ~p~, nhớ đầy đủ ~q~ lệnh theo đúng thứ tự, và biết rằng chiều cao của mình là ~m~. Hãy xác định vị trí mà Marin đáng ra phải đứng.

Input

Dòng đầu tiên chứa ba số nguyên dương ~n~, ~q~, ~m~.

Dòng thứ hai chứa ~n~ số ~p_1, p_2, \ldots, p_n~, tạo thành hoán vị ~p~.

Mỗi trong ~q~ dòng tiếp theo chứa hai số ~l_i~ và ~r_i~, mô tả lệnh thứ ~i~.

Output

In ra một số nguyên duy nhất: vị trí mà Marin phải đứng sau khi thực hiện xong toàn bộ các lệnh.

Ràng buộc

• ~1 \le n, q \le 10^5~
• ~1 \le m \le n~
• ~1 \le p_i \le n~
• ~1 \le l_i \le r_i \le n~

Chấm điểm

• Subtask 1 (7 điểm): ~n, q \le 1000~
• Subtask 2 (11 điểm): ~l_i = 1~ với mọi ~1 \le i \le q~
• Subtask 3 (17 điểm): ~m = 1~ hoặc ~m = n~
• Subtask 4 (24 điểm): ~n, q \le 5000~
• Subtask 5 (51 điểm): Không có ràng buộc bổ sung.

Sample Input 1

7 3 3
4 2 3 7 1 6 5
4 7
3 5
1 4

Sample Output 1

5

Sample Input 2

6 4 1
5 3 6 2 1 4
2 4
3 5
2 6
5 6

Sample Output 2

2

Sample Input 3

8 2 5
8 7 6 5 4 3 1 2
2 8
1 7

Sample Output 3

7

Giải thích

• Ví dụ 1: Sau lệnh đầu tiên, dãy chiều cao trong hàng là ~4~ ~2~ ~3~ ~1~ ~7~ ~5~ ~6~. Sau lệnh thứ hai, dãy trở thành ~4~ ~2~ ~1~ ~7~ ~3~ ~5~ ~6~. Sau lệnh cuối cùng, hàng cuối cùng là ~1~ ~7~ ~2~ ~4~ ~3~ ~5~ ~6~. Vì vậy Marin phải đứng ở vị trí thứ ~5~ tính từ trái sang.