题目描述

给一个正整数 $n$ ,数组 $a_i$,每次的左右端点 $l_i,r_i$

求：

$(\sum_{i=1}^{m}\sum_{j=l_{i}}^{r_{i}} a_{j}\times ((j-l_{i}+2)/2))\mod 29819$ 。

若取模后为负数，请加上 $29819$ 后输出。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个整数，数列 $A$ 。

第三行一个正整数 $m$ 。

第 $i+3$ 行，每行两个正整数 $l_{i},r_{i}$ ， $1 \le l_{i} \le r_{i} \le n,1 \le i \le m$ 。

输出格式

所求的值

样例 #1

样例输入 #1

5
7 -3 2 -5 8
2
2 4
1 5

样例输出 #1

11

样例 #2

样例输入 #2

10
3 1 -2 -5 1 3 -7 8 -9 -10
5
1 4
8 10
5 9
3 3
1 10

样例输出 #2

29676

对于 $100\%$ 的数据， $n \le 5 \times 10^6,m \le 3\times 10^6$ 。

时间限制:1.75s