リトルボーイズ

問題文

林くんから長さ$N$の整数列$A$が与えられます。

各$Q$個のクエリに対して、$A_{M_i}$を$[L_i, R_i)$内の中央値に置き換えた後、配列$A$の合計値を出力してください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 3$
• $1 \leq Q \leq 10^5$
• $0 \leq L_i \leq M_i \lt R_i \leq N$
• 入力はすべて整数

※テストケースは未作成です。