Marathon Training

Time limit: 0.2s Memory limit: 64MB Input: Output:

Luca has recently stepped up his training with the ultimate goal of being able to run a half marathon: as soon as he can, he goes out for a run. Since he always wears a fitness tracker, every time he trains the covered distance is automatically recorded in his favourite fitness application. So far, the details of NN training sessions have been captured. Among other information, one can see that in the ii-th session he ran for DiD_i kilometres.

Luca wants to analyse the progress to check whether he is getting better. Specifically, he would like to know how big is his longest improving streak. A sequence of consecutive training sessions, starting from the xx-th one and ending at the yy-th one, is an improving streak if Luca has run at least as many kilometres in the last session as in the first one and if he has covered at least DxD_x and at most DyD_y kilometres in every one of them (formally, DxDkDyD_x \leq D_k \leq D_y for each k=x,,yk = x, \dots, y).

How long is the longest improving streak Luca has recorded?

Input data

The first line contains the only integer NN, the number of training sessions recorded by Luca. The second line contains NN integers DiD_i, the distance covered in the ii-th training session.

Output data

You need to write a single line with an integer: the length of the longest improving streak of training sessions.

Constraints and clarifications

  • 1N100 0001 \leq N \leq 100 \ 000;
  • 1Di1091 \leq D_i \leq 10^9;
# Score Constraints
1 0 Examples
2 17 Di1D_i \leq 1 for each i=0N1i = 0 \dots N - 1
3 20 N500N \leq 500
4 26 N10 000N \leq 10 \ 000
5 37 No additional limitations.

Example 1

stdin

5
2 1 3 5 10

stdout

4

Explanation

In the first sample case, there is one improving streak of length four, consisting of the last four training sessions. In each of those four sessions Luca has run at least 11 and at most 1010 kilometres. No longer improving streaks exist.

Example 2

stdin

6
2 7 3 8 4 7

stdout

4

Explanation

In the second sample case, there is one improving streak of length four, composed of the first four training sessions. In the first four sessions, Luca has always run at least 22 and at most 88 kilometres. No longer improving streaks exist.

Log in or sign up to be able to send submissions!