10241: Достатня сума на відрізку
Реалізуйте дерево відрізків для знаходження накоротшого префіксу відрізку з заданою сумою.
Формат вхідних даних
В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 10^5\)).
В другому рядку елементи масиву. (\(0 \le Ai \le 10^5\))
В третьому рядку вводиться число \(P\) - кількість запитів (\(1 \le P \le 3*10^4\))
В кожному з наступних \(P\) рядків міститься по три числа - номера лівого і правого елементів відрізка масиву, та сума яку необхідно набрати на префіксі відрізка.
Формат вихідних даних
Для кожного запиту виведіть через пробіл - найменшу кількість елементів на префіксі запиту, які дадуть потрібну суму. Якщо таку суму на відрізку отримати неможливо, виведіть -1
Приклад вхідних даних
5
2 2 2 1 5
4
2 3 3
2 5 6
3 4 7
3 5 0
Приклад вихідних даних
2 4 -1 0
Пояснення до прикладу
В першому запиті на відрізку [2,3] необхідно набрати суму 3, для цього необхідно буде взяти обидва елемента 2+2=4 В другому запиті на відрізку [2,5] необхідно набрати суму 6, для цього необхідно буде взяти три елемента 2+1+5=8 В третьому запиті на відрізку [3,4] необхідно набрати суму 7, а це неможливо, бо сума всіх елеменітв відрізка 2+1=3 менша за 7 В четвертому запиті на відрізку [3,7] необхідно набрати суму 0, для цього потрібно - чисел
Коментарі