상한이 있는 정적 구간 합

크기가 $N$인 수열 $a_0, a_1, \dots, a _ {N - 1}$이 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리한다:

• $l$ $r$ $x$: $a_l,a_{l+1},...,a_{r-1}$의 원소 중 $x$ 이하인 원소의 개수와 합을 출력한다

제약 조건

• $1 \leq N, Q \leq 500000$
• $0 \leq a_i \leq 1000000000$
• $0 \leq l \leq r \leq N$
• $0 \leq x \leq 1000000000$

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$l_0$ $r_0$ $x_0$
$l_1$ $r_1$ $x_1$
:
$l_{Q-1}$ $r_{Q-1}$ $x_{Q-1}$

$l$ $r$ $x$: $a_l,a_{l+1},...,a_{r-1}$의 원소 중 $x$ 이하인 원소의 개수와 합을 출력한다