Expert.
Put your skills to the test.

Problem summary

For a contiguous subarray of length at least two, let max2 be its second-largest element counting duplicates. Maximize max2 minus the subarray length.

Source clarification. The statement prints N≥1 although no subarray of length at least two exists for N=1. No official convention for that degenerate input is supplied. The algorithm solves the defined N≥2 domain; its 0 output for N=1 is a defensive convention, not a claimed official answer.

Constraints

Printed bounds: 1 ≤ N ≤ 10^6; 1 ≤ ai ≤ 10^9. The objective is defined only when N≥2.

Worked example

Official example, transcribed with whitespace restored from the PDF.

5
3 1 4 1 59

1

Solution analysis

1. For any chosen pair of positions i<j, the interval between them has second-largest element at least min(ai,aj). Conversely, the two largest elements of any interval give a pair whose enclosing interval is no longer and has the same second-largest value. Thus it suffices to maximize min(ai,aj)−(j−i+1) over pairs.
2. Fix a position as the smaller endpoint value. Among positions on either side with value at least its value, only the nearest can improve its score. Two monotonic-stack scans find nearest greater-or-equal elements on the left and right in linear time: pop strictly smaller values, then the remaining top is the required neighbor.
3. In the sample, value 4 at position 3 has the nearest greater-or-equal value 59 at position 5. Their interval has length three and score 4−3=1. Equal elements must remain eligible, because duplicates count in the second maximum.

Why it works

Shrinking an interval to the positions of its two largest elements cannot decrease its score, proving that an optimum occurs among enclosing intervals of pairs. For each pair, designate a smaller endpoint; the nearest endpoint of at least that value on the same side gives at least as good a score. The stack scans inspect precisely these nearest candidates, hence at least one candidate attains the global optimum, and every inspected pair is itself a valid subarray.

Watch out. Pop strictly smaller values, not equal values. The printed N=1 bound leaves the required output undefined; code prints 0 defensively for that case.

An independently written complete program with standard headers.

// Key idea: Shrinking an interval to the positions of its two largest elements cannot decrease its
// score, proving that an optimum occurs among enclosing intervals of pairs. For each pair, designate a
// smaller endpoint; the nearest endpoint of at least that value on the same side gives at least as
// good a score.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n);
    for(auto&x:a){
        cin>>x;
    }
    if(n<2){
        cout<<0<<'\n';
        return 0;
    }
    long long answer=numeric_limits<long long>::lowest();
    vector<int>stack;
    for(int i=0;i<n;++i){
        while(!stack.empty()&&a[stack.back()]<a[i]){
            stack.pop_back();
        }
        if(!stack.empty()){
            answer=max(answer,a[i]-(i-stack.back()+1));
        }
        stack.push_back(i);
    }
    stack.clear();
    for(int i=n-1;i>=0;--i){
        while(!stack.empty()&&a[stack.back()]<a[i]){
            stack.pop_back();
        }
        if(!stack.empty()){
            answer=max(answer,a[i]-(stack.back()-i+1));
        }
        stack.push_back(i);
    }
    cout<<answer<<'\n';
}