E - ビルの見晴らし 解説 /

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

配点 : 466 点

問題文

高橋君は都市計画の調査員です。一直線の通りに沿って N 棟のビルが一列に並んでいます。左から順にビル 1 , ビル 2 , ... , ビル N と番号が付けられており、ビル i の高さは H_i です。すべてのビルの高さは互いに異なります。

各ビル i （ 1 \leq i \leq N ）について、「見晴らしスコア」 を以下のように定義します。

まず、ビル i から見て右方向（番号が i より大きい側）にある、ビル i よりも高いビルのうち、最も近いものをビル R_i とします。すなわち、 R_i は H_j > H_i を満たす j > i のうち最小の j です。該当するビルが存在しない場合、 R_i は存在しないものとします。

同様に、ビル i から見て左方向（番号が i より小さい側）にある、ビル i よりも高いビルのうち、最も近いものをビル L_i とします。すなわち、 L_i は H_j > H_i を満たす j < i のうち最大の j です。該当するビルが存在しない場合、 L_i は存在しないものとします。

直感的には、ビル i の見晴らしスコアは、ビル i を含み、左右それぞれ自分より高いビル（または通りの端）に到達するまでの連続する区間に含まれるビルの棟数です。具体的には、次のように定まります。

  • L_i と R_i の両方が存在する場合：スコアは R_i - L_i - 1（ビル L_i とビル R_i の間にあるビルの棟数）
  • R_i のみ存在し L_i が存在しない場合：スコアは R_i - 1（ビル 1 からビル R_i - 1 までのビルの棟数）
  • L_i のみ存在し R_i が存在しない場合：スコアは N - L_i（ビル L_i + 1 からビル N までのビルの棟数）
  • どちらも存在しない場合：スコアは N（すべてのビルの棟数）

高橋君は Q 個の質問に答える必要があります。各質問では整数 X_k が与えられ、見晴らしスコアが X_k 以上であるビルの棟数 を答えてください。

制約

  • 1 \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 ）
  • H_i はすべて互いに異なる
  • 1 \leq X_k \leq N （ 1 \leq k \leq Q ）
  • 入力はすべて整数である

入力

N Q
H_1 H_2 \cdots H_N
X_1
X_2
\vdots
X_Q
  • 1 行目には、ビルの棟数を表す整数 N と質問の数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各ビルの高さを表す整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。すべての H_i は互いに異なる。
  • 3 行目から Q 行にわたって、各質問の値を表す整数 X_k が 1 行に 1 つずつ与えられる。

出力

Q 行出力せよ。 k 行目（ 1 \leq k \leq Q ）には、第 k 番目の質問に対する答え、すなわち見晴らしスコアが X_k 以上であるビルの棟数を出力せよ。

入力例 1

5 4
3 1 4 2 5
1
2
3
5

出力例 1

5
3
2
1

入力例 2

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

出力例 2

7
3
2
1

入力例 3

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

出力例 3

10
6
4
2
1

入力例 4

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

出力例 4

15
8
4
1
1
1

入力例 5

1 1
1000000000
1

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is a surveyor for urban planning. Along a straight street, N buildings stand in a row. They are numbered Building 1, Building 2, ..., Building N from left to right, and the height of Building i is H_i. All building heights are distinct.

For each Building i (1 \leq i \leq N), we define a "view score" as follows.

First, among the buildings to the right of Building i (those with numbers greater than i) that are taller than Building i, let Building R_i be the nearest one. That is, R_i is the smallest j > i such that H_j > H_i. If no such building exists, then R_i does not exist.

Similarly, among the buildings to the left of Building i (those with numbers less than i) that are taller than Building i, let Building L_i be the nearest one. That is, L_i is the largest j < i such that H_j > H_i. If no such building exists, then L_i does not exist.

Intuitively, the view score of Building i is the number of buildings in the contiguous interval containing Building i that extends left and right until reaching a taller building (or the end of the street) in each direction. Specifically, it is determined as follows:

  • If both L_i and R_i exist: the score is R_i - L_i - 1 (the number of buildings between Building L_i and Building R_i)
  • If only R_i exists and L_i does not exist: the score is R_i - 1 (the number of buildings from Building 1 to Building R_i - 1)
  • If only L_i exists and R_i does not exist: the score is N - L_i (the number of buildings from Building L_i + 1 to Building N)
  • If neither exists: the score is N (the total number of buildings)

Takahashi needs to answer Q questions. For each question, an integer X_k is given. Answer the number of buildings whose view score is at least X_k.

Constraints

  • 1 \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)
  • All H_i are distinct
  • 1 \leq X_k \leq N (1 \leq k \leq Q)
  • All input values are integers

Input

N Q
H_1 H_2 \cdots H_N
X_1
X_2
\vdots
X_Q
  • The first line contains two integers separated by a space: N, the number of buildings, and Q, the number of questions.
  • The second line contains N integers H_1, H_2, \ldots, H_N separated by spaces, representing the heights of the buildings. All H_i are distinct.
  • The following Q lines each contain a single integer X_k, representing the value for each question.

Output

Output Q lines. On the k-th line (1 \leq k \leq Q), output the answer to the k-th question, that is, the number of buildings whose view score is at least X_k.

Sample Input 1

5 4
3 1 4 2 5
1
2
3
5

Sample Output 1

5
3
2
1

Sample Input 2

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

Sample Output 2

7
3
2
1

Sample Input 3

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

Sample Output 3

10
6
4
2
1

Sample Input 4

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

Sample Output 4

15
8
4
1
1
1

Sample Input 5

1 1
1000000000
1

Sample Output 5

1