問題文

$N$本の紐が、$Q$組あります。全ての組の紐にはそれぞれ数 $A_1, A_2, … ,A_N$ が書かれています。
$Q$個のクエリが次のように与えられます:

• L R … $j(1 \leq j \leq Q)$ についてこの時、$j$番目の組の、$L$番目から$R$番目の紐を反転させます。

例えば、$A=\{1,2,6,3\}, L=2, R=4$ の場合、$\{2,6,3\}$ の部分を反転させるので $\{1,3,6,2\}$ になります。

pura君は隣りあう $2$ つの紐を選んで位置を入れ替えることを繰り返して紐を反転させたいです。この操作だけで紐を反転できることは保証されています。
しかし、$A_i$の紐と$A_{i+1}$の紐を入れ替える時に、$A_i$に書かれた数$+A_{i+1}$に書かれた数　のコストがかかります。
pura君はこの操作で全ての組の紐をクエリ通りに入れ替えます。すべてのクエリを終えた後のコストの総和の最小値を出力してください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i \leq 10^5$
• $1 \leq L_j \lt R_j \leq N$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

すべてのクエリを終えた後のコスト総和の最小値を標準出力に出力してください。 コストの総和の最小値は $10^{18}$ 以下になることが保証されています。

入力例

$1$ 番目から $2$ 番目までを反転させるには、$1$ 番目と $2$ 番目を入れ替えればよいです。 この時にかかるコストは、コスト$A_1+$コスト$A_2 ＝ 3$ となり、$3$ が答えです。

それぞれ $\{1,4,2\}$ と書かれた紐の組が、$2$ つあります。クエリ通りに部分的に反転させ、それぞれ $\{4,1,2\}, \{1,2,4\}$ にしたいです。
一つ目のクエリは $1$ 本目と $2$ 本目を入れ替えれば達成されるのでコストは $5$ 、二つ目のクエリは $2$ 本目と $3$ 本目を入れ替えれば達成されるのでコストは $6$ になり、合計は $11$です。
クエリごとに別のひもの組になっていることに注意してください。