Expected Damage
Contest: Educational Codeforces Round 95 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, combinatorics, probabilities

You are playing a computer game. In this game, you have to fight $$$n$$$ monsters.

To defend from monsters, you need a shield. Each shield has two parameters: its current durability $$$a$$$ and its defence rating $$$b$$$. Each monster has only one parameter: its strength $$$d$$$.

When you fight a monster with strength $$$d$$$ while having a shield with current durability $$$a$$$ and defence $$$b$$$, there are three possible outcomes:

- if $$$a = 0$$$, then you receive $$$d$$$ damage;
- if $$$a > 0$$$ and $$$d \ge b$$$, you receive no damage, but the current durability of the shield decreases by $$$1$$$;
- if $$$a > 0$$$ and $$$d < b$$$, nothing happens.

The $$$i$$$-th monster has strength $$$d_i$$$, and you will fight each of the monsters exactly once, in some random order (all $$$n!$$$ orders are equiprobable). You have to consider $$$m$$$ different shields, the $$$i$$$-th shield has initial durability $$$a_i$$$ and defence rating $$$b_i$$$. For each shield, calculate the expected amount of damage you will receive if you take this shield and fight the given $$$n$$$ monsters in random order.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of monsters and the number of shields, respectively.

The second line contains $$$n$$$ integers $$$d_1$$$, $$$d_2$$$, ..., $$$d_n$$$ ($$$1 \le d_i \le 10^9$$$), where $$$d_i$$$ is the strength of the $$$i$$$-th monster.

Then $$$m$$$ lines follow, the $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le n$$$; $$$1 \le b_i \le 10^9$$$) — the description of the $$$i$$$-th shield.

Output format:
Print $$$m$$$ integers, where the $$$i$$$-th integer represents the expected damage you receive with the $$$i$$$-th shield as follows: it can be proven that, for each shield, the expected damage is an irreducible fraction $$$\dfrac{x}{y}$$$, where $$$y$$$ is coprime with $$$998244353$$$. You have to print the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is the inverse element for $$$y$$$ ($$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 2
1 3 1
2 1
1 2

Example output:
665496237
1

Example input:
3 3
4 2 6
3 1
1 2
2 3

Example output:
0
8
665496236

Editorial:
First of all, let's find a solution in $$$O(nm)$$$. We will use the lineriality of expectation: the answer for some shield $$$j$$$ is equal to $$$\sum\limits_{i = 1}^{n} d_i P(i, j)$$$, where $$$P(i, j)$$$ is the probability that the monster $$$i$$$ will deal damage if we use the $$$j$$$-th shield. Let's see how to calculate $$$P(i, j)$$$.
Consider a monster $$$i$$$ such that $$$d_i \ge b_j$$$. To deal damage, he should be preceded by at least $$$a_j$$$ other monsters having $$$d_i \ge b_j$$$. We can write a complicated formula with binomial coefficients to calculate the probability of this happening, and then simplify it, but a much easier solution is to consider the order of these "strong" monsters. Suppose there are $$$k$$$ of them, then there are $$$\max(k - a_j, 0)$$$ strong monsters that will deal damage. Since all orderings are equiprobable, the probability that our fixed monster will deal damage is $$$\dfrac{\max(k - a_j, 0)}{k}$$$ — since it is the probability that it will take one of the last places in the order.
Okay, what about "weak" monsters? It turns out that we can use the same approach: to deal damage, a weak monster should be preceded by at least $$$a_j$$$ strong monsters. Consider the relative order of $$$k$$$ strong monsters and that weak monster we are analyzing. There are $$$\max(k + 1 - a_j, 0)$$$ positions where the weak monster will deal damage, so the probability of weak monster dealing damage is $$$\dfrac{\max(k + 1 - a_j, 0)}{k + 1}$$$.
Okay, we got a solution in $$$O(nm)$$$. How to make it faster? Whenever we consider a shield, all monsters are split into two types: strong and weak, and we may sort the monsters beforehand, so the number of strong monsters (and their total strength) can be found with binary search. Since the probabilities for all strong monsters are the same, we can multiply their total strength by the probability that one fixed strong monster will deal damage (we already described how to calculate it). The same applies for the weak monsters, so the total complexity is $$$O(n \log n + m (\log n + \log MOD))$$$.