B - 果樹園の収穫区間 解説 /

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

配点 : 233 点

問題文

高橋君は果樹園の管理人として働いています。この果樹園には N 本の果物の木が一列に並んでおり、左から順に木 1, 木 2, \ldots, 木 N と番号が付けられています。木 i (1 \leq i \leq N) には果実がちょうど 1 つ実っており、その糖度は T_i です。

高橋君は、出荷基準を満たす果実だけを収穫したいと考えています。果実の糖度が L 以上 R 以下であるとき、かつそのときに限り、その果実は出荷基準を満たします。

高橋君は、番号が連続する木の区間を選び、その区間内のすべての果実を収穫しようとしています。具体的には、整数 l, r (1 \leq l \leq r \leq N) を選び、木 l, 木 l+1, \ldots, 木 r からなる区間を考えます。この区間内のすべての木の果実が出荷基準を満たすとき、この区間は収穫可能であるといいます。

収穫可能な区間に含まれる木の本数 r - l + 1 の最大値を求めてください。収穫可能な区間が 1 つも存在しない場合は 0 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq R \leq 10^9
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N L R
T_1 T_2 \ldots T_N
  • 1 行目には、木の本数を表す整数 N、出荷基準の糖度の下限（以上）を表す整数 L、出荷基準の糖度の上限（以下）を表す整数 R が、スペース区切りで与えられる。
  • 2 行目には、各木の果実の糖度を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

収穫可能な区間に含まれる木の本数の最大値を 1 行で出力してください。収穫可能な区間が存在しない場合は 0 を出力してください。

入力例 1

5 10 20
15 12 18 25 14

出力例 1

3

入力例 2

10 5 15
8 10 12 7 9 20 6 11 13 14

出力例 2

5

入力例 3

15 100 500
150 200 300 250 180 50 400 350 300 200 150 100 450 600 200

出力例 3

7

Score : 233 pts

Problem Statement

Takahashi works as a manager of an orchard. In this orchard, there are N fruit trees lined up in a row, numbered Tree 1, Tree 2, \ldots, Tree N from left to right. Tree i (1 \leq i \leq N) bears exactly one fruit with a sweetness level of T_i.

Takahashi wants to harvest only the fruits that meet the shipping standard. A fruit meets the shipping standard if and only if its sweetness level is at least L and at most R.

Takahashi plans to select a contiguous interval of consecutively numbered trees and harvest all the fruits within that interval. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and considers the interval consisting of Tree l, Tree l+1, \ldots, Tree r. If all fruits on the trees within this interval meet the shipping standard, the interval is called harvestable.

Find the maximum number of trees r - l + 1 contained in a harvestable interval. If no harvestable interval exists, output 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq R \leq 10^9
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N L R
T_1 T_2 \ldots T_N
  • The first line contains the integer N representing the number of trees, the integer L representing the lower bound (inclusive) of the sweetness level for the shipping standard, and the integer R representing the upper bound (inclusive) of the sweetness level for the shipping standard, separated by spaces.
  • The second line contains the integers T_1, T_2, \ldots, T_N representing the sweetness levels of the fruits on each tree, separated by spaces.

Output

Output in one line the maximum number of trees contained in a harvestable interval. If no harvestable interval exists, output 0.

Sample Input 1

5 10 20
15 12 18 25 14

Sample Output 1

3

Sample Input 2

10 5 15
8 10 12 7 9 20 6 11 13 14

Sample Output 2

5

Sample Input 3

15 100 500
150 200 300 250 180 50 400 350 300 200 150 100 450 600 200

Sample Output 3

7