Mountain tourism#221
The active tourism club on the planet Olympia decided to offer clients routes along a scenic mountain ridge. The ridge is quite long and traversing it in one go is difficult, so the club seeks to find the most attractive route of limited length. According to social research, tourists most enjoy hiking for the longest possible distance in places that are higher than the surrounding areas, as this allows for better views and creates a sense of elevation.
To simplify the problem, the ridge has been divided into one-meter segments and the average altitude above sea level of each segment has been determined.
The numerical attractiveness of each segment is defined as the total number of consecutive segments to both the left and right, starting from its immediate neighbors, that have strictly lower altitude than the segment itself. The segment itself is not included in this total. The attractiveness of a route is calculated as the sum of the attractiveness values of all one-meter segments included in it. The length of a route must not exceed meters. The direction of the route does not matter, as it does not affect attractiveness. The route can start at any segment of the ridge and must be continuous — that is, it must consist of consecutive segments without gaps.
The first line contains two integers: — the total length of the ridge in meters, and (1 \leq T \leq N \leq 100\,000) — the maximum allowed route length. The second line contains integers, each from to 10^6, representing the heights of the consecutive one-meter segments.
Output a single integer: the numerical attractiveness of the most appealing route of length at most along the mountain ridge.
Example 1