Hôm nay cuối tuần được nghỉ học, Tý và Tèo chơi trò xếp thẻ như sau: có ~n~ tấm thẻ được xếp thành một hàng trên bàn, đánh số từ ~1~ đến ~n~. Trên thẻ thứ ~j~ có ghi một số nguyên ~p_j~ ~(1 \le p_j \le n; j = 1, 2, \dots, n)~, không có hai thẻ nào có cùng giá trị. Tức là giá trị ghi trên các thẻ là một hoán vị của các số nguyên trong đoạn ~[1, n]~.

Trò chơi gồm ~q~ lượt, lượt thứ ~i~ sẽ sắp xếp lại thứ tự của những thẻ từ ~l_i~ đến ~r_i~ như sau: Đầu tiên, Tý lấy ra các thẻ có số thứ tự trong đoạn ~[l_i, r_i]~. Tiếp theo, Tý đưa các thẻ này trở lại hàng theo quy tắc: Vị trí ~l_i~ là thẻ có giá trị bé nhất trong số những thẻ vừa lấy ra; vị trí ~l_i + 1~ là thẻ có giá trị lớn nhất trong số những thẻ còn lại; vị trí ~l_i + 2~ là thẻ có giá trị bé nhất trong số những thẻ còn lại; vị trí ~l_i + 3~ là thẻ có giá trị lớn nhất trong số những thẻ còn lại; Tiếp tục xen kẽ thẻ bé nhất – thẻ lớn nhất – thẻ bé nhất – thẻ lớn nhất – ... cho đến vị trí thứ ~r_i~.

Yêu cầu: Tý đố Tèo đoán vị trí của tấm thẻ có ghi số ~m~ trên bàn sau khi kết thúc trò chơi. Em hãy lập trình giúp Tèo tìm nhé!

Input

• Dòng đầu tiên gồm ba số nguyên ~n, q, m~ ~(1 \le n, q \le 10^5; 1 \le m \le n)~;

• Dòng thứ hai gồm ~n~ số nguyên ~p_1, p_2, \dots, p_n~ là một hoán vị của các số từ ~1~ đến ~n~;

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo gồm hai số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~, mô tả lượt chơi thứ ~i~.

Các số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Output

Một số nguyên là vị trí của thẻ có ghi số ~m~ sau khi kết thúc trò chơi.

Scoring

Sample Input 1

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

Sample Output 1

6

Notes

Ban đầu, giá trị trên các thẻ là: ~4, 2, 3, 7, 1, 6, 5~.

Sau lượt 1: ~4, 2, 3, 1, 7, 5, 6~.

Sau lượt 2: ~4, 2, 1, 7, 3, 5, 6~.

Sau lượt 3: ~1, 7, 2, 4, 3, 5, 6~.

Thẻ có ghi số ~5~ đang ở vị trí thứ ~6~.