IOI 2077 Team Selection Expected Teammate Sum

There are n candidate contestants numbered from 1 to n. Each candidate has a distinct ability value. They are sorted in increasing order by their ability values, i.e. a_i < a_i+1 for 1 ≤ i < n.

For the official contest, a contiguous segment of candidates [l,r] is chosen to participate, and one of these candidates, with index k (l ≤ k ≤ r), is designated as “small A”. Thus, there are s = r-l+1 contestants in total.

Small A will randomly choose a nonnegative integer m uniformly from the set \(\{0,1,\dots,\lfloor \frac{s-1}{2} \rfloor\}\) and then randomly select 2m teammates from the s-1 other contestants. However, he imposes the condition that his own ability value \(a_k\) must be the median of the \(2m+1\) team members. Notice that since the candidates are sorted, this means that among the selected teammates exactly m must have ability values less than \(a_k\) and exactly m must have values greater than \(a_k\>.

Because small A wishes the total ability sum of his teammates to be as high as possible, if he could choose optimally among all valid teams, he would take the largest m candidates from the lower part and the largest m candidates from the upper part (where "largest" means those with higher ability values) among the contestants in the segment.

Formally, let the ability values be \(a_1,a_2,\dots,a_n\) (with \(a_1 < a_2 < \dots < a_n\)). For a query described by three numbers \(l, r, k\) (with \(l ≤ k ≤ r\)), define:

• \(s = r-l+1\);
• \(M = \lfloor\frac{s-1}{2}\rfloor\);
• \(L = k-l\) (the number of contestants in \([l,r]\) with ability less than \(a_k\));
• \(R = r-k\) (the number of contestants in \([l,r]\) with ability greater than \(a_k\));
• \(m_0 = \min(M, L, R)\) – the maximum possible valid m for which the team can be formed.

For any valid m (≥1) (if \(m_0 \ge 1\); note that when \(m_0 = 0\) the only possibility is m=0 and the team has no teammates, giving a sum of 0), the optimal team is chosen as follows:

• The m teammates from the lower part are those with indices from \(k-m\) to \(k-1\) (i.e. the m candidates with the highest ability values that are less than \(a_k\)). Their total ability sum is \(P(k-1) - P(k-m-1)\), where \(P(i)=a_1+a_2+\cdots+a_i\) and \(P(0)=0\).
• The m teammates from the upper part are those with indices from \(r-m+1\) to \(r\) (i.e. the m candidates with the highest ability values among those greater than \(a_k\)). Their total ability sum is \(P(r) - P(r-m)\).

Thus, for a fixed m (with \(1 \le m \le m_0\)) the optimal total summation of selected teammates is:

[ S(m)=\bigl(P(k-1)-P(k-m-1)\bigr)+\bigl(P(r)-P(r-m)\bigr). ]

The expected total ability sum (over the random choice of m from \(\{0,1,\dots,M\}\)) is then given by:

[ E = \frac{\sum_{m=0}^{m_0} S(m)}{M+1} \quad (\text{with } S(0)=0). ]

Since the answer may be fractional, compute it modulo \(998244353\) (the modular inverse exists under this prime modulus). Moreover, you are given q queries, and for each query you must compute the corresponding expected value as above. Finally, output the XOR (bitwise exclusive OR) of the answers for all queries (when each answer is represented as an integer modulo \(998244353\)).

Input Format:

• The first line contains an integer \(n\) — the number of candidates.
• The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\) in strictly increasing order.
• The third line contains an integer \(q\) — the number of queries.
• Each of the next \(q\) lines contains three integers \(l, r, k\) (with \(l \le k \le r\)) describing a query.

Output Format:

• Output a single integer — the XOR of the answers for all queries, where each answer is computed modulo \(998244353\).

Note on Implementation: It is recommended to precompute prefix sums \(P\) where \(P(i)=a_1+\cdots+a_i\) to quickly compute the sums over intervals. Additionally, to efficiently sum over many values, consider a second-level prefix sum (or cumulative sum) array. Use Fermat's little theorem to compute modular inverses modulo \(998244353\).

inputFormat

The input begins with an integer n (number of candidates). The next line contains n space‐separated integers \(a_1, a_2, \dots, a_n\) in strictly increasing order. The third line contains an integer q (number of queries). Each of the following q lines contains three integers l, r, k (with l ≤ k ≤ r) describing a query.

outputFormat

Output a single integer — the XOR (bitwise exclusive OR) of the expected teammate sum values for all queries, with each expectation computed modulo \(998244353\).

sample

5
1 3 5 7 9
3
1 5 3
2 4 3
3 5 3

665496243