23134번 - Interval Shuffle 다국어

Kanade has a sequence $A_{1...n}$ and $m$ intervals $[L_i, R_i]$ of indices from $1$ to $n$, bounds included. He does $m$ operations in sequence, one for each interval. For the $i$-th operation, Kanade can choose and perform one of the following two actions:

1. Choose $x \in [L_i, R_i]$ and update $A_x := A_x + 1$.
2. Rearrange $A_{L_i...R_i}$ in any order Kanade wants.

Now Kanade wants to know the maximum value of $A_{k}$ after these operations. Find the answer for each $k \in [1, n]$.

The first line of input contains two integers $n$ and $m$, the size of the sequence and the number of operations ($1 \leq n, m \leq 2 \cdot 10^5$). The second line contains $n$ integers $A_{1...n}$, the initial sequence ($0 \leq A_i \leq 2 \cdot 10^5$).

Then follow $m$ lines. The $i$-th of them contains two integers $L_i$ and $R_i$ describing the respective interval ($1 \leq L_i \leq R_i \leq n$).

Output $n$ integers, the $i$-th of which is the maximum possible value of $A_{i}$ after $m$ operations.