Masala #2NXRXEQHUC
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.
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)\)
Masala javobi alohida qatorlarda chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 3 7 20 14 8 2 1 3 1 4 1 |
2 1 0 |
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 kanalimizga obuna bo'ling