\(n\) học sinh có chiều cao đôi một khác nhau từ \(1\) đến \(n\), ban đầu theo hoán vị \(p\). Mỗi lệnh \((l,r)\) lấy các học sinh ở đoạn vị trí \([l,r]\), rồi điền lại từ trái sang phải bằng người thấp nhất còn lại, người cao nhất còn lại, người thấp nhất còn lại, ... xen kẽ. Biết chiều cao \(m\) của Marin, hãy xác định vị trí của Marin sau khi thực hiện lần lượt mọi lệnh.

Dữ liệu vào

Dòng đầu chứa \(n,q,m\) (\(1\le n,q\le10^5\), \(1\le m\le n\)). Dòng hai là hoán vị \(p\) gồm \(n\) số. Mỗi trong \(q\) dòng tiếp theo chứa \(l,r\) (\(1\le l\le r\le n\)).

Dữ liệu ra

In vị trí cuối cùng của Marin.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(7\) điểm: \(n,q\le1000\).
2. \(11\) điểm: mọi \(l_i=1\).
3. \(17\) điểm: \(m=1\) hoặc \(m=n\).
4. \(24\) điểm: \(n,q\le5000\).
5. \(51\) điểm: không có ràng buộc thêm.

Ví dụ

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

5

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

2

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

7

Nguồn

COCI 2025/2026 - Vòng 4, bài Tjelesni.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.