Expert.
Put your skills to the test.

Problem summary

Employees arrive in order 1 through N. Employee i shakes hands with exactly ai of the earlier employees. Friendship is symmetric. Among all friendship graphs consistent with these counts, find the largest possible degree of any employee and the smallest possible degree of any employee.

Constraints

2 ≤ N ≤ 200000; counts describe a possible arrival process, hence 0 ≤ ai ≤ i−1.

Worked example

Official sample; other valid outputs may exist.

5
0 0 1 1 1

3
0

Solution analysis

1. For a fixed employee i, its ai earlier friends are unavoidable. Each later employee j can include i if aj>0, and can exclude i unless aj=j−1, in which case every earlier employee must be a friend.
2. Therefore maximum degree of i is ai plus the number of later positive counts. Its minimum is ai plus the number of later fully connected counts. Process from right to left, keeping these two suffix counts, and take the global maximum and minimum.
3. In the first sample employee 2 can be chosen by employees 3,4,5, achieving degree 3. Employee 1 can be excluded by all of them, achieving degree 0.

Why it works

For a later employee j, choosing its aj earlier friends is independent of choices made for other employees. Thus all optional inclusions of i can simultaneously be made, and all optional exclusions can simultaneously be made. This proves the fixed-employee bounds are attainable. Taking extrema over employees gives precisely the requested global extrema.

Watch out. The maximum and minimum may occur in different graphs. Count later full rows against their own number of predecessors.

An independently written complete program with standard headers.

// Key idea: For a later employee j, choosing its aj earlier friends is independent of choices made for
// other employees. Thus all optional inclusions of i can simultaneously be made, and all optional
// exclusions can simultaneously be made.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int&value:a){
        cin>>value;
    }
    int positive=0,forced=0;
    int maximum=0,minimum=n;
    for(int i=n-1;i>=0;--i){
        maximum=max(maximum,a[i]+positive);
        minimum=min(minimum,a[i]+forced);
        if(a[i]>0){
            ++positive;
        }
        if(a[i]==i){
            ++forced;
        }
    }
    cout<<maximum<<'\n'<<minimum<<'\n';
}