005 - A lot of lamps

この問題にはいくつかの部分点が設定されています。

問題

$10^{100}$個のランプがあり、左から順に$1,2,3,...10^{100}$と番号が振られています。
最初、$N$個のランプ$A_1,A_2,...A_N$のみが光っており、その他のランプは光っていません。
$1 \leq i \leq Q$を満たす全ての整数$i$について、ちょうど1回ずつ以下の操作を行います。
・$L_i \leq j \leq R_i$を満たす全ての整数$j$について、$j$番のランプが光っているなら光を消し、光っていないのならば光らせる。
全ての操作が終わった後のランプの光り方は一意に定まるので、光っているランプの個数を答えてください。

入力

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

$N$ $Q$
$A_1$ $A_2$ ... $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
...
$L_Q$ $R_Q$

1行目に整数$N,Q$が与えられる。
2行目に$N$個の整数$A_1,A_2,...A_N$が与えられる。
3行目から$Q$行にわたって整数$L_i,R_i(1 \leq i \leq Q)$が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $0 \leq N \leq 5×10^4$
• $1 \leq Q \leq 5×10^4$
• $1 \leq A_i \leq 10^9 (1 \leq i \leq N)$
• $1 \leq L_i \leq R_i \leq 10^9 (1 \leq i \leq Q)$
• 入力はすべて整数

部分点1(100点)の入出力ケースについて以下を満たす。

• $Q=1$

入出力例

入力例1

5 1
1 3 5 7 9
1 3

出力例1

4

最初、1,3,5,7,9番のランプが光っています。1番から3番までのランプに操作をすると、光っているランプは2,5,7,9番の4つになるので4を出力します。
この入力例は部分点1の制約を満たします。

入力例2

7 4
6 9 12 5 2 23 47
1 16
100 500
41 696
1 5

出力例2

265