E - Stable Arrangement of Cargo Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は倉庫で荷物の管理を担当しています。倉庫には N 個の荷物が一列に並んでおり、左から順に荷物 1 、荷物 2 、...、荷物 N と番号がついています。

各荷物 i には重さがあり、その重さは整数 A_i で表されます。

高橋君は、連続した荷物をまとめて棚に積み上げる作業を行います。棚に積む荷物の区間 [l, r] が「安定配置」であるとは、以下の条件を満たすことを指します：

  • 区間内の各荷物 j （ l < j \leq r ）について、 l \leq i < j かつ A_i \leq A_j となる荷物 i が少なくとも 1 つ存在する。

これは、各荷物が自分より左にある区間内のいずれかの荷物を支えとして安定して積めることを意味します。重さが同じか軽い荷物の上には、その荷物以上の重さの荷物を安定して積むことができます。最も左の荷物は棚の底に直接置くため、この条件の対象外です。

青木君は高橋君に Q 個の質問をしました。各質問では区間 [L_k, R_k] が与えられ、この区間に完全に含まれる連続部分区間のうち、安定配置となるものの個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_k \leq R_k \leq N (1 \leq k \leq Q)
  • 入力はすべて整数

入力

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、荷物の個数を表す N と、質問の個数を表す Q が、スペース区切りで与えられる。
  • 2 行目には、各荷物の重さを表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から Q 行にわたって、各質問の区間 [L_k, R_k] が与えられる。
  • 2 + k 行目では、 k 番目の質問の左端 L_k と右端 R_k がスペース区切りで与えられる。

出力

Q 行出力してください。 k 行目には、 k 番目の質問に対する答え、すなわち区間 [L_k, R_k] に完全に含まれる連続部分区間のうち、安定配置となるものの個数を出力してください。

入力例 1

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

出力例 1

11
4
6
3

入力例 2

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

出力例 2

6
1
4
2

入力例 3

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

出力例 3

23
10
12
13
11
1
12
8

入力例 4

30 12
15 3 8 8 20 1 2 2 2 25 10 10 5 30 4 6 6 12 11 40 7 7 7 50 9 18 18 17 60 1
1 30
1 15
16 30
5 20
10 25
2 9
12 18
21 29
6 6
14 24
3 27
28 30

出力例 4

192
53
68
81
55
20
14
36
1
42
160
4

入力例 5

1 1
1000000000
1 1

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is in charge of managing packages in a warehouse. There are N packages lined up in a row in the warehouse, numbered from left to right as package 1, package 2, ..., package N.

Each package i has a weight represented by an integer A_i.

Takahashi performs the task of stacking consecutive packages onto a shelf. An interval [l, r] of packages to be placed on the shelf is called a "stable arrangement" if it satisfies the following condition:

  • For each package j in the interval (l < j \leq r), there exists at least one package i such that l \leq i < j and A_i \leq A_j.

This means that each package can be stably stacked using some package to its left within the interval as support. A package can be stably stacked on top of another package that has the same or lighter weight. The leftmost package is placed directly on the bottom of the shelf, so it is exempt from this condition.

Aoki asked Takahashi Q questions. For each question, an interval [L_k, R_k] is given. Find the number of contiguous subintervals completely contained within this interval that form a stable arrangement.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_k \leq R_k \leq N (1 \leq k \leq Q)
  • All inputs are integers

Input

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains N, the number of packages, and Q, the number of questions, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the weights of each package, separated by spaces.
  • The following Q lines contain the interval [L_k, R_k] for each question.
  • The (2 + k)-th line contains the left endpoint L_k and right endpoint R_k of the k-th question, separated by a space.

Output

Print Q lines. On the k-th line, print the answer to the k-th question, that is, the number of contiguous subintervals completely contained within the interval [L_k, R_k] that form a stable arrangement.

Sample Input 1

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

Sample Output 1

11
4
6
3

Sample Input 2

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

Sample Output 2

6
1
4
2

Sample Input 3

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

Sample Output 3

23
10
12
13
11
1
12
8

Sample Input 4

30 12
15 3 8 8 20 1 2 2 2 25 10 10 5 30 4 6 6 12 11 40 7 7 7 50 9 18 18 17 60 1
1 30
1 15
16 30
5 20
10 25
2 9
12 18
21 29
6 6
14 24
3 27
28 30

Sample Output 4

192
53
68
81
55
20
14
36
1
42
160
4

Sample Input 5

1 1
1000000000
1 1

Sample Output 5

1