I - Buildings 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

ビル 1, ビル 2, \ldots, ビル N の N 棟がこの順で東西に一列に並んでおり、ビル 1 が最も西に、ビル N が最も東に建っています。ビル i\ (1\leq i\leq N) の高さは H_i です。

整数の組 (i,j)\ (1\leq i\lt j\leq N) に対して、以下の条件を満たすとき ビル i からビル j を見ることができます。

  • ビル i とビル j の間にビル j より高いビルが存在しない。すなわち、H_k\gt H_j を満たす整数 k\ (i\lt k\lt j) が存在しない。

Q 個の質問に答えてください。i 番目の質問では整数の組 (l_i,r_i)\ (l_i\lt r_i) が与えられるので、ビル r_i より東にあるビル（ビル r_i+1, ビル r_i+2,\ldots,ビル N ）のうちビル l_i とビル r_i の両方から見ることができるものの個数を答えてください。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq Q\leq 2\times 10^5
  • 1\leq H_i\leq N
  • H_i\neq H_j\ (i\neq j)
  • 1\leq l_i\lt r_i\leq N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
H_1 H_2 \ldots H_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行出力せよ。i\ (1\leq i\leq Q) 行目には i 番目の質問に対する答えを出力せよ。

入力例 1

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

出力例 1

2
0
1
  • 1 つ目の質問について、ビル 2 より東にあるビルのうち ビル 1 とビル 2 の両方から見ることができるものはビル 3,5 の 2 つです。
  • 2 つ目の質問について、ビル 5 より東にあるビルは存在しません。
  • 3 つ目の質問について、ビル 4 より東にあるビルのうち、ビル 1,4 の両方から見ることができるビルはビル 5 の 1 つです。

入力例 2

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

出力例 2

1
3
1
2
1
0
1
1
0
0

Score : 550 points

Problem Statement

There are N buildings, building 1, building 2, \ldots, building N, arranged in this order in a straight line from west to east. Building 1 is the westernmost, and building N is the easternmost. The height of building i\ (1\leq i\leq N) is H_i.

For a pair of integers (i,j)\ (1\leq i\lt j\leq N), building j can be seen from building i if the following condition is satisfied.

  • There is no building taller than building j between buildings i and j. In other words, there is no integer k\ (i\lt k\lt j) such that H_k > H_j.

You are given Q queries. In the i-th query, given a pair of integers (l_i,r_i)\ (l_i\lt r_i), find the number of buildings to the east of building r_i (that is, buildings r_i + 1, r_i + 2, \ldots, N) that can be seen from both buildings l_i and r_i.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq H_i \leq N
  • H_i\neq H_j\ (i\neq j)
  • 1 \leq l_i < r_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
H_1 H_2 \ldots H_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query.

Sample Input 1

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

Sample Output 1

2
0
1
  • For the first query, among the buildings to the east of building 2, buildings 3 and 5 can be seen from both buildings 1 and 2, so the answer is 2.
  • For the second query, there are no buildings to the east of building 5.
  • For the third query, among the buildings to the east of building 4, building 5 can be seen from both buildings 1 and 4, so the answer is 1.

Sample Input 2

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

Sample Output 2

1
3
1
2
1
0
1
1
0
0