E - Mountain Range Vista Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は山岳写真家です。東西に一直線に連なる山脈があり、西から東へ順に 1 から N までの番号がついた N 個の山があります。山 i の標高は H_i です。

高橋君は Q 回の撮影を計画しています。各撮影 j では、山 L_j から山 R_j までの区間を対象とし、この区間を西側（左側）から眺めて写真を撮ります。

西側から山並みを眺めたとき、区間 [L_j, R_j] に含まれる山 k（L_j \le k \le R_j）が見えるとは、区間内でそれより西側にある山のうち、山 k より厳密に高いものが存在しないことを意味します。形式的には、L_j \le m < k かつ H_m > H_k を満たす m が存在しないとき、山 k は見えます。特に、区間の左端の山 L_j は常に見えます。

言い換えると、区間 [L_j, R_j] の標高の列を左から順に見ていき、その時点までの最大標高以上の標高をもつ山に出会うたびに数を 1 増やすとき、最終的な数が見える山の個数です。

各撮影について、見える山の個数を求めてください。

制約

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

入力

N Q
H_1 H_2 \ldots H_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、山の数を表す整数 N とクエリの数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各山の標高を表す整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
  • 3 行目から Q 行にわたり、各撮影の区間の左端 L_j と右端 R_j を表す整数がスペース区切りで与えられる。

出力

Q 行出力せよ。j 行目には、j 番目の撮影で見える山の個数を出力せよ。

入力例 1

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

出力例 1

3
3
2
1

入力例 2

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

出力例 2

2
4
3
3
2

入力例 3

12 10
5 1 5 7 3 7 8 2 8 6 9 4
1 12
1 4
2 7
3 9
4 10
5 12
6 9
7 11
8 12
10 12

出力例 3

7
3
5
5
4
5
3
3
3
2

入力例 4

40 25
12 7 15 15 3 20 18 20 25 1 25 24 30 5 6 30 29 31 31 2 40 35 40 41 10 9 42 42 8 50 49 50 51 11 52 52 4 60 59 60
1 40
1 10
1 20
5 25
10 30
15 40
2 39
3 8
6 13
9 16
11 23
14 28
17 33
20 37
21 40
22 32
24 35
26 38
28 40
30 40
31 36
33 39
34 40
36 38
38 40

出力例 4

23
6
11
12
12
16
22
4
5
4
7
10
11
11
12
7
7
9
8
7
5
4
5
2
2

入力例 5

2 1
1000000000 1000000000
1 2

出力例 5

2

Score : 466 pts

Problem Statement

Takahashi is a mountain photographer. There is a mountain range stretching in a straight line from west to east, consisting of N mountains numbered 1 to N from west to east. The elevation of mountain i is H_i.

Takahashi is planning Q photo shoots. For each photo shoot j, he targets the interval from mountain L_j to mountain R_j, and takes a photo viewing this interval from the west side (left side).

When viewing the mountain range from the west side, a mountain k (L_j \le k \le R_j) within the interval [L_j, R_j] is visible if there is no mountain to its west within the interval that is strictly taller than mountain k. Formally, mountain k is visible if there is no m satisfying L_j \le m < k and H_m > H_k. In particular, the leftmost mountain L_j of the interval is always visible.

In other words, if you scan the sequence of elevations in the interval [L_j, R_j] from left to right, incrementing a counter each time you encounter a mountain whose elevation is greater than or equal to the maximum elevation seen so far, the final count is the number of visible mountains.

For each photo shoot, determine the number of visible mountains.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq H_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
H_1 H_2 \ldots H_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains an integer N representing the number of mountains and an integer Q representing the number of queries, separated by a space.
  • The second line contains integers H_1, H_2, \ldots, H_N representing the elevation of each mountain, separated by spaces.
  • The following Q lines each contain integers representing the left endpoint L_j and right endpoint R_j of each photo shoot's interval, separated by a space.

Output

Output Q lines. On the j-th line, output the number of visible mountains in the j-th photo shoot.

Sample Input 1

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

Sample Output 1

3
3
2
1

Sample Input 2

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

Sample Output 2

2
4
3
3
2

Sample Input 3

12 10
5 1 5 7 3 7 8 2 8 6 9 4
1 12
1 4
2 7
3 9
4 10
5 12
6 9
7 11
8 12
10 12

Sample Output 3

7
3
5
5
4
5
3
3
3
2

Sample Input 4

40 25
12 7 15 15 3 20 18 20 25 1 25 24 30 5 6 30 29 31 31 2 40 35 40 41 10 9 42 42 8 50 49 50 51 11 52 52 4 60 59 60
1 40
1 10
1 20
5 25
10 30
15 40
2 39
3 8
6 13
9 16
11 23
14 28
17 33
20 37
21 40
22 32
24 35
26 38
28 40
30 40
31 36
33 39
34 40
36 38
38 40

Sample Output 4

23
6
11
12
12
16
22
4
5
4
7
10
11
11
12
7
7
9
8
7
5
4
5
2
2

Sample Input 5

2 1
1000000000 1000000000
1 2

Sample Output 5

2