Maximum Unsorted Subarray

Problem Description

Given an array A of non-negative integers of size N. Find the minimum sub-array Al, Al+1 ,..., Ar such that if we sort(in ascending order) that sub-array, then the whole array should get sorted. If A is already sorted, output -1.



Problem Constraints

1 <= N <= 1000000
1 <= A[i] <= 1000000



Input Format

First and only argument is an array of non-negative integers of size N.



Output Format

Return an array of length two where the first element denotes the starting index(0-based) and the second element denotes the ending index(0-based) of the sub-array. If the array is already sorted, return an array containing only one element i.e. -1.



Example Input

Input 1:

A = [1, 3, 2, 4, 5]

Input 2:

A = [1, 2, 3, 4, 5]


Example Output

Output 1:

[1, 2]

Output 2:

[-1]


Example Explanation

Explanation 1:

If we sort the sub-array A1, A2, then the whole array A gets sorted.

Explanation 2:

A is already sorted.

bool helper(vector<int>&v,int i){
    int x=v[i];
    if(i==0)return x>v[1];
    else if(i==v.size()-1)return x<v[i-1];
    return x>v[i+1] || x<v[i-1];
}

vector<int> Solution::subUnsort(vector<int> &v) {
    if(v.size()<2)return {-1};
    int st,end;
    vector<int>ans;
    int smallest=INT_MAX,largest=INT_MIN;
    for(int i=0; i<v.size(); i++){
        if(helper(v,i)){
            smallest=min(smallest,v[i]);
            largest=max(largest,v[i]);
        }
    }
    if(smallest==INT_MAX)return {-1};
    int left=0,right=v.size()-1;
    while(smallest>=v[left])left++;
    while(largest<=v[right])right--;
    return {left,right};
    
}