Problem
n elemanlı bir permütasyon verildiğinde.
l'den r'ye bir permütasyon alt segmenti için ters çevirme sayısıyla ilgili m soruyu yanıtlayın.
Bir inversiyon, i < olacak şekilde i, j indeks çiftidir. j ve a
i > a
j, burada a
i permütasyonun i. öğesidir.
Giriş:
İlk satır n sayısını içerir (1 <= n <= 10
5).
İkinci satır, n öğenin bir permütasyonunu içerir (permütasyonun öğeleri, 1'den n'ye kadar ikili olarak farklı tam sayılardır).
Üçüncü satır m sayısını içerir (1 <= m <= 10
5).
Sonraki m satır iki tamsayı l ve r içerir - sorgunun sınırları (1 <= l, r <= n).
Çıktı:
m satır yazdır - bu sorguların yanıtları.
Örnekler:
| Giriş |
Çıktı |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |