Masala #2NXRXEQHUC

Xotira 64 MB Vaqt 1000 ms Qiyinchiligi 1 %

0.0

Marafon

Marafonda N nafar ishtirokchi qatnashmoqda. Har bir ishtirokchiga 1 dan N gacha bo'lgan tartib raqami berilgan. Ishtirokchilarning joylashuvi $A$ massivida berilgan bo'lib, $A[i]$ ishtirokchining finish chizig'idan qancha uzoqda ekanligini ko'rsatadi (masofa kichik bo'lsa, finishga yaqinroq).

Sizga $T$ ta so'rov beriladi. Har bir so'rovda ikki ishtirokchining raqami (x, y) beriladi. Siz quyidagini aniqlashingiz kerak:

Agar x ishtirokchisi y ishtirokchisiga yetib olishi kerak bo'lsa, x ishtirokchisi finishga yaqinlashish davomida nechta ishtirokchini ortda qoldirishi kerakligini hisoblang.
Agar x ishtirokchisi allaqachon y ishtirokchisidan yaqinroq yoki teng masofada bo'lsa, natija 0 bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qator N va T sonlar beriladi. (N — ishtirokchilar soni, T — so'rovlar soni). $(1≤N,T≤10^5)$

Ikkinchi qator: $A_1,A_2, ..., A_N$ lar beriladi. (Ishtirokchilarning finish chizig'idan masofalari)

Keyingi T ta qatorda: x va y lar beriladi. $(1≤x,y≤N)$

Chiquvchi ma'lumotlar:

Masala javobi alohida qatorlarda chop eting.

Misollar

#	input.txt	output.txt
1	4 3 7 20 14 8 2 1 3 1 4 1	2 1 0

Izoh:

1-test.
4 3

7 20 14 8

1-so'rov (2, 1): 2-ishtirokchi finishga yetguncha, 3 va 4-ishtirokchilarni ortda qoldirishi kerak (javob: 2).

2-so'rov (3, 1): 3-ishtirokchi finishga yetguncha, faqat 4-ishtirokchini ortda qoldiradi (javob: 1).

3-so'rov (4, 1): 4-ishtirokchi allaqachon 1-ishtirokchidan yaqinroq (javob: 0).

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin