Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Camping Trip

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 1.0 seconds

Rin loves camping, and is planning to go on a camping trip. However, not all days are good for camping.

Any day with an average temperature between A and B degrees (inclusive) is considered to be a good day. All other days are bad days for camping.

Rin knows what the average temperature will be during each of the next N days, and would like to schedule her trip as an interval [L,R] within this period (1 \le L \le R \le N), where her trip starts on day L and ends on day R.

She would like to go on the longest trip possible, but she will only consider a trip where the number of good days is strictly greater than the number of bad days on her trip (including days L and R).

Please help Rin find the maximum length of any camping trip that satisfies this requirement.


The first line contains three space-separated integers, N, A, and B.

The second line contains N space-separated integers, t_1, t_2, \dots, t_N, where t_i is the average temperature of day i.


You should output a single integer – the maximum length of any camping trip over the next N days that satisfies Rin's requirement, or 0 if no such trip exists.


  • 1 \le N \le 200\,000
  • 0 \le A \le B \le 50
  • 0 \le t_i \le 50 for all i


  • Subtask 1 (15%): t_i \le t_{i+1} for all i
  • Subtask 2 (20%): N \le 100
  • Subtask 3 (25%): N \le 5\,000
  • Subtask 4 (40%): No further constraints apply

Sample Explanation

In the first sample case, the longest possible camping trip is [3,7] (starting on day 3 and ending on day 7), which is 5 days long. There are 3 good days and 2 bad days on this trip, which meets Rin's requirement.

In the second sample case, there are two possible solutions – [1,3] and [6,8], which are both 3 days long.

Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.

  • Sample Input 1

    7 21 23
    18 18 19 20 21 22 22

    Sample Output 1

  • Sample Input 2

    8 21 23
    22 24 23 20 20 19 21 22

    Sample Output 2