| OMORI CONTEST |
|---|
| Finished |
After achieving the title "Employee of the Month" three times, Mr. Jawsum promoted Hero to "Manager of Cryptocurrencies" as a reward for his hard work. Hero then found an opportunity to earn money using a new coin called "NEAR".
To gain NEAR, you need to work on some tasks related to training "Artificial Intelligence" to solve problems related to "Competitive Programming"; there are $$$n$$$ types of tasks to work on, the $$$i$$$-th type of tasks $$$(1 \le i \le n)$$$ has a "Profit value" equal to $$$a_i$$$.
Since Hero is currently the "Manager of Cryptocurrencies", he has enough power to hire people to work for him. Due to "The Last Resort" policies, the employees he hires can only work in a specific range $$$[l, r]$$$, meaning they can only work on tasks of type $$$i$$$ such that $$$(l \le i \le r)$$$.
The way Hero hires employees is as follows: he first chooses a range $$$[l, r]$$$ $$$(1 \le l \le r \le n)$$$, and then hires $$$\frac{x(x+1)}{2}$$$ employees such that $$$x$$$ is equal to the size of the range $$$(r - l + 1)$$$; he hires each of the $$$\frac{x(x+1)}{2}$$$ to work on all distinct sub-ranges in the range $$$[l, r]$$$. If an employee works on a range $$$[L, R]$$$, the total amount of money he achieves after working for one day is equal to $$$\text{LCM}(a_L, a_{L+1}, a_{L+2}, ..., a_{R-1}, a_R) \times L \times R$$$ worth of NEAR, where $$$\text{LCM}$$$ is the Least Common Multiple.
At the end of the day, Hero collects all money gained from all of his hired employees. Now since Hero wants to maximize his profit, he thought that he needed to choose the whole array of types of tasks as the initial range he hires people in. But he forgot that in "Dreamspace", every bank account has a limit of $$$998244352$$$ NEAR coins. When the number of coins in an account exceeds that number, it overflows and bounces back to $$$0$$$ NEAR coins. So the actual profit Hero gets is equal to the gained profit taken under modulo $$$998244353$$$.
Hero chose $$$Q$$$ candidate ranges as initial ranges to hire people in; the $$$j$$$-th $$$(1 \le j \le Q)$$$ range is equal to $$$[l_j, r_j]$$$ , and he wants to find the final profit he gets at the end of the day if he chooses that range, modulo $$$998244353$$$.
More formally, the answer to the $$$j$$$-th query is equal to $$$\displaystyle\sum_{L = l_j}^{r_j}\sum_{R = L}^{r_j} \text{LCM}(a_L, a_{L+1}, a_{L+2}, ..., a_{R-1}, a_R) \times L \times R$$$ taken under modulo $$$998244353$$$.
The first line of input contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of types of tasks.
The next line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^6)$$$ separated by spaces — the profit values of each type of the tasks.
The next line contains one integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ — the number of candidate ranges Hero chose.
The $$$j$$$-th line of the next $$$Q$$$ lines each contains two integers $$$l_j, r_j$$$ $$$(1 \le l_j \le r_j \le n)$$$ — the boundaries of the $$$j$$$-th candidate range.
Output $$$Q$$$ lines; the $$$j$$$-th of them should contain the final profit obtained from choosing the $$$j$$$-th range taken under modulo $$$998244353$$$.
3 1 2 3 3 1 2 2 3 1 3
13 71 94
4 2 2 3 3 4 1 1 1 2 1 3 1 4
2 14 95 251
In the third query of the first sample, there are $$$6$$$ subranges in $$$[1,3]$$$, which are $$$\{ \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 2, 3\}\}$$$; the accumulative $$$\text{LCM}$$$ of each of them is equal to $$$\{1, 2, 3, 2, 6, 6\}$$$; the sum of each subarray $$$\text{lcm}$$$ multiplied by both its boundaries is equal to : $$$1\times 1 \times 1 + 2 \times 2 \times 2 + 3 \times 3 \times 3 + 2 \times 1 \times 2 + 6 \times 2 \times 3 + 6 \times 1 \times 3 = 94$$$
Mr. Jawsum congratulating Hero after promoting him to "Manager of Cryptocurrencies"
