Weather Trends

Interview

Time limit20sMemory limit1024 MB

Summary

Given n daily temperatures and a window of m days, find the largest rise from an earlier day to a later day within that window.

Level: Medium5 of 10
Topics: Sliding window, Queue, Array
Solved: No attempts yet

Problem

George is an aspiring meteorologist who is passionate about analyzing temperature data. He must find the largest temperature increase within specific time frames. Help him build an efficient algorithm that computes these increases for any time interval.

Given daily temperature measurements over n days, George wants the greatest temperature increase within a window of m days. In other words, find the maximum temperature difference between two days, where the second day is no more than m days after the first one.

Input

The first line contains a single integer n, the number of temperature measurements. The second line contains a single integer m, the maximum time interval in days. The third line contains n temperature values separated by spaces.

Output

Output a single real number: the maximum temperature increase within the specified m-day interval. The absolute or relative error must be at most $10^{-6}$ .

Your task is to implement an efficient algorithm that solves this problem for George.

Examples2

Example 1

Input

10
6
30 28 30 29 32 26 27 30 28 33

Expected output

7.000000

Example 2
Input
```
7
3
31 32 33 25.91 31 30 35
```
Expected output
```
5.090000
```