Məşhur ICPC Komandası Yenidən
Mr. B, Mr. G və Mr. M 2012 ACM-ICPC Dünya Final Yarışmasına hazırlaşarkən, Mr. B gündəlik təlimləri üçün geniş bir yarışma problemləri dəsti toplamışdı. Təlimə başlayanda, Mr. B bu dəstdən bir problem seçərdi. Problem dəstindəki bütün problemlər nəşr olunma vaxtına görə sıralanmışdı. Hər dəfə məşqçiləri Prof. S, onlara müəyyən bir zaman intervalında nəşr olunan bir problemi seçmələrini tapşırardı. Yəni, əgər problemlər bir sıra ilə sıralanmışsa, hər dəfə onlar həmin sıranın müəyyən bir seqmentindən birini seçməli olurdular.
Bundan əlavə, problemləri toplayarkən, Mr. B hər problemin çətinlik dərəcəsini də bilirdi. Ondan bir problem seçməsi istənildikdə, əgər ən asanını seçsəydi, Mr. G "Hey, nə qədər triviyal bir problem!" deyə şikayət edərdi; əgər ən çətinini seçsəydi, Mr. M onu bitirmək üçün çox vaxt sərf etdiyini deyə narazılıq edərdi. Bu dilemmanı həll etmək üçün, Mr. B orta çətinlikdə olanı seçməyə qərar verdi. Buna görə də, o, verilən ardıcıllığın müəyyən intervalında median ədədi bilməyə ehtiyac duyurdu.
Giriş verilənləri
Hər test üçün, ilk sətir n (1 ≤ n ≤ 100000) tək bir tam ədədini ehtiva edir, bu da problemlərin ümumi sayını göstərir. İkinci sətir n tam ədədlərini x_i (0 ≤ x_i ≤ 1000000000), tək boşluqla ayrılmış, hər problemin çətinliyini göstərir, artıq nəşr vaxtına görə sıralanmışdır. Növbəti sətir m (1 ≤ m ≤ 100000) tək bir tam ədədini ehtiva edir, sorğuların sayını göstərir. Sonra m sətir gəlir, hər sətir bir cüt tam ədəd, A və B (1 ≤ A ≤ B ≤ n), göstərir ki, Mr. B A və B mövqeləri arasında (daxil olmaqla, mövqelər 1-dən sayılır) bir problem seçməlidir. A və B arasında olan elementlərin sayının tək olduğu təmin edilir.
Çıxış verilənləri
Hər sorğu üçün, Mr. B-nin seçməli olduğu problemin çətinliyini göstərən bir tam ədəd çıxış edin.