Дана последовательность целых чисел \([a_1, a_2, \dots, a_n]\). Обозначим \(s(l,r)\) как сумму элементов от \(a_l\) до \(a_r\) (т. е. \(s(l,r) = \sum\limits_{i=l}^{r} a_i\)).
Построим другую последовательность \(b\) размером \(\frac{n(n+1)}{2}\) следующим образом: \(b = [s(1,1), s(1,2), \dots, s(1,n), s(2,2), s(2,3), \dots, s(2,n), s(3,3), \dots, s(n,n)]\).
Например, если \(a = [1, 2, 5, 10]\), то \(b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10]\).
Вам даны \(q\) запросов. В \(i\)-м запросе вам даны два целых числа \(l_i\) и \(r_i\), и вам нужно вычислить \(\sum \limits_{j=l_i}^{r_i} b_j\).