Grając w grę logiczną, masz do czynienia z $n$ kamieniami szlachetnymi ustawionymi w rzędzie, ponumerowanymi od $1$ do $n$ od lewej do prawej. $i$-ty kamień ma kolor $c[i]$.
W dowolnym momencie możesz wybrać dwa sąsiadujące kamienie tego samego koloru i usunąć je. Następnie kamienie znajdujące się po obu stronach usuwanej pary zsuwają się, zamykając lukę, co może doprowadzić do powstania nowych sąsiadujących par.
Otrzymasz $q$ niezależnych scenariuszy. W $j$-tym scenariuszu bierzesz pod uwagę tylko kamienie od $l[j]$ do $r[j]$. Zakładając, że wykonasz optymalną sekwencję usunięć, jaka jest minimalna liczba kamieni, która może pozostać?
Wejście
Twój program musi czytać dane ze standardowego wejścia.
Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ i $q$.
Druga linia wejścia zawiera $n$ liczb całkowitych $c[1], c[2], \dots, c[n]$.
Kolejne $q$ linii wejścia zawiera po dwie liczby całkowite. $i$-ta z tych linii zawiera $l[i]$ oraz $r[i]$.
Wyjście
Twój program musi wypisać wynik na standardowe wyjście.
Wyjście powinno zawierać $q$ linii. $i$-ta z tych linii powinna zawierać jedną liczbę całkowitą, będącą odpowiedzią dla $i$-tego scenariusza.
Podzadania
Dla wszystkich przypadków testowych dane wejściowe spełniają następujące warunki:
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ dla wszystkich $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ dla wszystkich $1 \le j \le q$
Twój program będzie testowany na instancjach spełniających następujące ograniczenia:
| Podzadanie | Wynik | Dodatkowe ograniczenia |
|---|---|---|
| 0 | 0 | Przykładowe przypadki testowe |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | Kamienie tego samego koloru tworzą spójny podciąg (Jeśli $c[i] = c[j]$ oraz $i < j$, to $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$ dla wszystkich $1 \le j \le q$ |
| 5 | 8 | Istnieją dokładnie dwa kamienie każdego koloru |
| 6 | 16 | $c[i] \le 2$ dla wszystkich $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | Brak dodatkowych ograniczeń |
Przykład
Wejście 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
Wyjście 1
1 0 1 4
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 3, 7, 8 i 9.
Kamienie $n = 8$ przedstawiono na poniższym diagramie.
W pierwszym scenariuszu należy wziąć pod uwagę tylko pierwsze trzy kamienie. Usunięcie dowolnych dwóch sąsiadujących kamieni pozostawi dokładnie jeden, po czym niemożliwe będzie usunięcie kolejnych kamieni. Stąd odpowiedź to 1.
W drugim scenariuszu kamienie można usunąć w następujący sposób, nie pozostawiając żadnego.
W trzecim scenariuszu kamienie można usunąć w następujący sposób, pozostawiając jeden.
W czwartym scenariuszu nie można usunąć żadnych kamieni. Stąd odpowiedź to 4.
Przykład 2
Wejście 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
Wyjście 2
2 0 0
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 3, 6, 7, 8 i 9.