C - 花壇の同色チェック 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は学校の花壇の管理を任されている。花壇には一列に N 個の区画があり、左から i 番目（ 1 \leq i \leq N ）の区画には色 C_i の花が植えられている。ここで、花の色は正の整数で表される。

青木君は花壇の見栄えを調査するために、高橋君に Q 個の質問をした。花壇において、隣り合う 2 つの区画に同じ色の花が植えられていると、見た目の変化が少なく単調に見えてしまう。そこで青木君は、指定した範囲内に、隣り合う区画の花の色が同じである箇所がいくつあるかを知りたいと考えている。

j 番目（ 1 \leq j \leq Q ）の質問では、区画 L_j から区画 R_j までの範囲が指定される。この範囲の中で、 L_j \leq i \leq R_j - 1 かつ C_i = C_{i+1} を満たす整数 i の個数を求めてほしい。すなわち、区画 L_j から区画 R_j までの連続した区間に含まれる隣り合う区画の組のうち、花の色が一致しているものの数を答えることになる。

Q 個の質問それぞれに対して答えを求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq L_j < R_j \leq N （ 1 \leq j \leq Q ）
  • 入力はすべて整数である。

入力

N Q
C_1 C_2 \ldots C_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、区画の数を表す整数 N と質問の数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各区画の花の色を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、 j 番目の質問で指定される範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行にわたって出力してください。 j 行目（ 1 \leq j \leq Q ）には、 j 番目の質問に対する答え、すなわち L_j \leq i \leq R_j - 1 かつ C_i = C_{i+1} を満たす整数 i の個数を出力してください。

入力例 1

5 3
1 1 2 2 2
1 5
1 3
3 5

出力例 1

3
1
2

入力例 2

8 5
3 3 3 1 2 2 1 1
1 8
2 5
1 4
5 8
3 6

出力例 2

4
1
2
2
1

入力例 3

15 8
10 10 5 5 5 3 3 7 7 7 7 1 1 2 2
1 15
1 5
5 10
10 15
3 7
2 14
6 8
1 2

出力例 3

9
3
3
3
3
7
1
1

Score : 333 pts

Problem Statement

Takahashi is in charge of managing the school's flower bed. The flower bed has N plots arranged in a row, and the i-th plot from the left (1 \leq i \leq N) has a flower of color C_i planted in it. Here, flower colors are represented by positive integers.

Aoki asked Takahashi Q questions to investigate the appearance of the flower bed. In the flower bed, if two adjacent plots have flowers of the same color, there is little visual variation and it looks monotonous. Therefore, Aoki wants to know how many places within a specified range have adjacent plots with the same flower color.

In the j-th question (1 \leq j \leq Q), a range from plot L_j to plot R_j is specified. Find the number of integers i satisfying L_j \leq i \leq R_j - 1 and C_i = C_{i+1}. In other words, among the pairs of adjacent plots within the contiguous interval from plot L_j to plot R_j, count the number of pairs where the flower colors match.

Find the answer for each of the Q questions.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
  • All input values are integers.

Input

N Q
C_1 C_2 \ldots C_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains the integer N representing the number of plots and the integer Q representing the number of questions, separated by a space.
  • The second line contains the integers C_1, C_2, \ldots, C_N representing the flower color of each plot, separated by spaces.
  • In the following Q lines, the j-th line contains the left endpoint L_j and the right endpoint R_j of the range specified in the j-th question, separated by a space.

Output

Output Q lines. On the j-th line (1 \leq j \leq Q), output the answer to the j-th question, that is, the number of integers i satisfying L_j \leq i \leq R_j - 1 and C_i = C_{i+1}.

Sample Input 1

5 3
1 1 2 2 2
1 5
1 3
3 5

Sample Output 1

3
1
2

Sample Input 2

8 5
3 3 3 1 2 2 1 1
1 8
2 5
1 4
5 8
3 6

Sample Output 2

4
1
2
2
1

Sample Input 3

15 8
10 10 5 5 5 3 3 7 7 7 7 1 1 2 2
1 15
1 5
5 10
10 15
3 7
2 14
6 8
1 2

Sample Output 3

9
3
3
3
3
7
1
1