Реалізуйте sqrt-декомпозицію запитів (алгоритм Мо) для знаходження кількості інверсій на відрізу.

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів перестановки (\(1 \le N \le 50000\)).
В другому рядку елементи відповідної перестановки. (\(1 \le Ai \le N\))
В третьому рядку вводиться число \(K\) - кількість запитів (\(1 \le K \le 30000\))
В кожному з наступних \(K\) рядків міститься по два числа - номера лівого і правого елементів відрізка перестановки

Формат вихідних даних

Для кожного запиту виведіть через пробіл - відповідь на запит

Приклад вхідних даних

5
3 1 4 5 2 
3
2 4
1 4
3 3

Приклад вихідних даних

0 1 0