Задача №1614. Продажа недвижимости
На прямой улице находятся \(N\) только что построенных домов, которые выставлены на продажу. Для каждого дома известна его цена. Однако нашлось немало богатых покупателей, которые хотели бы приобрести для себя несколько подряд идущих домов и вопросы вида "сколько будет стоить покупка домов от номера \(i\) до номера \(j\)" стали попадаться все чаще и чаще. В фирму, продающую дома, пришло \(k\) писем с вопросами о ценах на дома или группы домов. Напишите программу, которая обработает эти письма за разумное время.
сначала вводится число \(N\) – количество домов (натуральное, не превышает \(10^6\)). Затем вводится \(N\) чисел – цена каждого дома (натуральное, не превышает 1000). В следующей строке вводится число \(k\) – количество писем (натуральное, не превышает \(10^6\)). Далее идет \(k\) строк по 2 числа в каждой – номера начального и конечного дома на интервале. Гарантируется, что номера домов корректны.
для каждого запроса в отдельной строке выведите суммарную стоимость всех домов на указанном участке.