Maximum Satisfaction Score

You are given an integer sequence \(a\) of length \(n\). For any contiguous subarray \([l, r]\) (i.e. taking the chapters from index \(l\) to \(r\)), its satisfaction score is defined as:

[ S(l,r)=\max{a_l,a_{l+1},\ldots,a_r}-\min{a_l,a_{l+1},\ldots,a_r}-(r-l+1). ]

Your task is to choose a contiguous subarray so that the satisfaction score is maximized, and output this maximum value.

Note: Even if the maximum satisfaction score is negative, output the maximum value you can achieve.

inputFormat

The first line contains an integer \(n\) representing the number of chapters.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the evaluation scores of each chapter.

outputFormat

Output a single integer, the maximum satisfaction score obtainable by choosing a contiguous subarray of the given sequence.

sample

1
5

-1