あなたは、$n$ 個の宝石が一列に並んだパズルゲームをプレイしています。宝石には左から右へ $1$ から $n$ までの番号が振られており、$i$ 番目の宝石の色は $c[i]$ です。
任意の時点で、隣り合う同じ色の宝石を2つ選んで削除することができます。宝石を削除すると、その両側の宝石が詰まり、新たに隣り合うペアができる可能性があります。
$q$ 個の独立したシナリオが与えられます。$j$ 番目のシナリオでは、$l[j]$ 番目から $r[j]$ 番目までの宝石のみを考慮します。最適な削除手順を行った場合、残る宝石の最小数はいくつになるでしょうか。
入力
プログラムは標準入力から読み込む必要があります。
入力の最初の行には、2つの整数 $n$ と $q$ がスペース区切りで含まれます。 2行目には、$n$ 個の整数 $c[1], c[2], \dots, c[n]$ がスペース区切りで含まれます。 続く $q$ 行の各行には、2つの整数が含まれます。$i$ 番目の行には $l[i]$ と $r[i]$ が含まれます。
出力
プログラムは標準出力に出力する必要があります。
出力は $q$ 行からなる必要があります。$i$ 番目の行には、$i$ 番目のシナリオに対する答えを整数で出力してください。
制約
すべてのテストケースにおいて、入力は以下の範囲を満たします。
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- すべての $1 \le i \le n$ に対して $1 \le c[i] \le 10^9$
- すべての $1 \le j \le q$ に対して $1 \le l[j] \le r[j] \le n$
プログラムは、以下の制限を満たす入力インスタンスに対してテストされます。
| 小課題 | スコア | 追加の制約 |
|---|---|---|
| 0 | 0 | サンプルテストケース |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | 同じ色の宝石は連続する部分配列をなす (もし $c[i] = c[j]$ かつ $i < j$ ならば $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | すべての $1 \le j \le q$ に対して $l[j] = 1$ |
| 5 | 8 | 各色の宝石はちょうど2つ存在する |
| 6 | 16 | すべての $1 \le i \le n$ に対して $c[i] \le 2$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | 追加の制約なし |
入出力例
入力 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
出力 1
1 0 1 4
注記
このテストケースは小課題 3, 7, 8, 9 で有効です。
$n = 8$ 個の宝石を以下の図に示します。
最初のシナリオでは、最初の3つの宝石のみを考慮します。隣り合う同じ色の宝石を削除するとちょうど1つが残り、その後はこれ以上宝石を削除することはできません。したがって、答えは 1 です。
2番目のシナリオでは、以下のように宝石を削除することで、何も残さないことができます。
3番目のシナリオでは、以下のように宝石を削除することで、1つを残すことができます。
4番目のシナリオでは、宝石を削除することはできません。したがって、答えは 4 です。
入力 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
出力 2
2 0 0
注記
このテストケースは小課題 3, 6, 7, 8, 9 で有効です。