У Ярослава есть массив p = p1, p2, ..., pn (1 ≤ pi ≤ n), состоящий из n различных целых чисел. Также есть m запросов:
Помогите Ярославу, ответьте на все его запросы.
В первой строке записаны целые числа n и m (1 ≤ n, m ≤ 2·105). Во второй строке записаны n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n). В следующих m строках заданы запросы Ярослава. В i-той строке записаны целые числа li, ri (1 ≤ li ≤ ri ≤ n).
Выведите m целых чисел — ответы на запросы Ярослава в порядке их следования во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
1 1 1 1 1
1
10 9 1 2 3 4 5 6 7 8 9 10 1 10 2 9 3 8 4 7 5 6 2 2 9 10 5 10 4 10
27 14 8 4 2 1 2 7 9
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач