你正在進行一個益智遊戲，遊戲中有 $n$ 個排成一列的寶石，從左到右編號為 $1$ 到 $n$。第 $i$ 個寶石的顏色為 $c[i]$。
在任何時候，你可以選擇兩個顏色相同的相鄰寶石並將它們刪除。接著，兩側的寶石會向中間滑動以填補空隙，這可能會產生新的相鄰寶石對。
你將會收到 $q$ 個獨立的場景。在第 $j$ 個場景中，你只考慮從第 $l[j]$ 個寶石開始到第 $r[j]$ 個寶石結束的範圍。假設你執行最佳的刪除序列，請問最少會剩下多少顆寶石？
輸入格式
你的程式必須從標準輸入讀取資料。
第一行包含兩個以空格分隔的整數 $n$ 和 $q$。
第二行包含 $n$ 個以空格分隔的整數 $c[1], c[2], \dots, c[n]$。
接下來的 $q$ 行，每行包含兩個以空格分隔的整數。第 $i$ 行包含 $l[i]$ 和 $r[i]$。
輸出格式
你的程式必須輸出到標準輸出。
輸出應包含 $q$ 行。第 $i$ 行應包含一個整數，即第 $i$ 個場景的答案。
資料範圍
對於所有測試資料，輸入滿足以下限制：
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ 對於所有 $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ 對於所有 $1 \le j \le q$
你的程式將在滿足以下限制的輸入實例上進行測試：
| 子任務 | 分數 | 額外限制 |
|---|---|---|
| 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 | $l[j] = 1$ 對於所有 $1 \le j \le q$ |
| 5 | 8 | 每種顏色恰好有兩顆寶石 |
| 6 | 16 | $c[i] \le 2$ 對於所有 $1 \le i \le n$ |
| 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
說明 1
此測試資料適用於子任務 3、7、8 和 9。$n = 8$ 顆寶石如下圖所示。
在第一個場景中，只考慮前三顆寶石。刪除任何兩個相鄰的寶石會剩下剛好一顆，之後便無法再刪除任何寶石。因此，答案為 1。
在第二個場景中，寶石可以按以下方式刪除，最後不留任何寶石：
在第三個場景中，寶石可以按以下方式刪除，最後留下一顆寶石：
在第四個場景中，沒有寶石可以被刪除。因此，答案為 4。
輸入格式 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
輸出格式 2
2 0 0
說明 2
此測試資料適用於子任務 3、6、7、8 和 9。