Ski Trip

Katerina wants to go skiing. The ski resort is far from her house, so she takes her skis on her shoulder and decides to go to the mountain by cog railway. The railway makes stops at N points on the mountain. Any two consecutive stops are one kilometer apart. For each stop i (where 1 ~\le~ i ~\le~ N), we know the altitude Y~_i~ at which it is located.

As the railway moves up the mountain, Katerina can get off in the morning at any stop she wants, ski in the opposite direction, and board again at some previous stop when it returns in the afternoon to return home. However, to be able to ski, the stop she gets off at must not be at a lower altitude than the one she boards at again.

Katerina loves skiing. Help her find the longest route she can take.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the data N and Y~_i~ and calculates the length of the longest route Katerina can take.

Input Files:

The input file named skitrip.in is a text file containing two lines. The first line contains a single integer N, the number of points where the railway makes a stop. The second line contains N integers Y~_i~ (where 1 ~\le~ i ~\le~ N) separated in pairs by a single space, the altitudes of the stop points.

Output Files:

The output file named skitrip.out is a text file consisting of a single line that must contain exactly one integer: the length of the longest route Katerina can take. If there is no valid route (because the altitudes of the stop points decrease as the railway moves), then the answer must be zero.

Example of Input - Output Files

STDIN (skitrip.in)

16
78 88 64 94 17 91 57 69 38 62 13 17 35 15 20 15

STDOUT (skitrip.out)

10

Explanation: Katerina can get off at the 15th stop, which has an altitude of Υ~_{15}~ = 20. From there, she can ski backward to the 5th stop, which has an altitude of Υ~_5~ = 17. This route is the longest she can take and has a length of 15-5 = 10 kilometers.

Constraints:

For the altitudes of the stations, the following will apply: 1 ~\le~ Υ~_i~ ~\le~ 1.000.000.000.

• For test cases worth 40%, of the total points, it will be:
  1 ~\le~ Ν ~\le~ 10.000
• For test cases worth 80%, of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1.000.000
• For test cases worth 100%, of the total points, it will be:
  1 ~\le~ Ν ~\le~ 2.000.000

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 128 MB.