Sum of Subarray Maximum Product

In a grand programming contest NOIP 2022, teams led by Little N and Little O each have n players numbered from 1 to n. The programing level of the i-th player in team N is \(a_i\) and in team O is \(b_i\). Both \(\{a_i\}\) and \(\{b_i\}\) form a permutation of \(\{1,2,\dots, n\}\).

Before each match, the judge (Little P) selects a range \([l,r]\) from 1 to n which determines the players invited from both teams. Then, during the contest, two parameters \(p,q\) (with \(l\le p\le q\le r\)) are chosen by a dice throw. Only players with numbers in \([p,q]\) can participate; and from each team, the player with the maximum programming level among those with numbers in \([p,q]\) will be chosen. If the chosen players have levels \(m_a\) and \(m_b\) respectively, then the excitement of the match is \(m_a \times m_b\).

There are \(Q\) matches. For each match, the parameters \(l\) and \(r\) are fixed while \(p,q\) are random (subject to \(l\le p\le q\le r\)). You are to calculate, for each match, the sum of the excitement over all possible choices of \(p,q\). Since the answer may be enormous, output the result modulo \(2^{64}\) (i.e. modulo 18446744073709551616).

Hint: For a fixed team (say team N), note that if you precompute for each index \(i\) the maximum range in which \(a_i\) is the maximum (using monotonic stacks), then the number of subarrays in which the \(i\)th player is the maximum is \((i - L_i) \times (R_i - i)\), where \(L_i+1\) and \(R_i-1\) denote the boundaries. A similar observation applies for team O. Finally, note that a subarray of indices \([p,q]\) is valid only if it contains the indices that yield the maximum in both teams and lies within the intersection of the valid ranges.

inputFormat

The input begins with a positive integer n indicating the number of players in each team. The next line contains n space‐separated integers \(a_1, a_2, \dots, a_n\) representing the programming levels of team N. The following line contains n space‐separated integers \(b_1, b_2, \dots, b_n\) representing the programming levels of team O. It is guaranteed that both \(\{a_i\}\) and \(\{b_i\}\) are a permutation of \(\{1,2,\dots,n\}\). The next line contains an integer Q representing the number of matches. Each of the next Q lines contains two integers l and r (with \(1 \le l \le r \le n\)) specifying a match.

outputFormat

For each match, output one line containing the sum of the excitement of all matches (i.e. the sum of \(m_a \times m_b\) over all subarrays \([p,q]\) with \(l \le p \le q \le r\)) modulo \(2^{64}\).

sample

3
1 3 2
2 1 3
2
1 2
2 3

8
18