腾讯 小Q的排序 排序

题目描述

小Q在学习许多排序算法之后灵机一动决定自己发明一种排序算法，小Q希望能将n个不同的数排序为升序。小Q发明的排序算法在每轮允许两种操作：

1、 将当前序列中前n-1个数排为升序

2、 将当前序列中后n-1个数排为升序

小Q可以任意次使用上述两种操作，小Q现在想考考你最少需要几次上述操作可以让序列变为升序。

输入描述:

输入包括两行，第一行包括一个正整数n(3≤n≤10^5)，表示数字的个数第二行包括n个正整数a[i](1≤a[i]≤10^9)，即需要排序的数字，保证数字各不相同。

输出描述:

输出一个正整数，表示最少需要的操作次数

示例1

输入

6
4 3 1 6 2 5

输出

2

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int brr[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            cin>>arr[i];
            brr[i]=arr[i];
        }
        sort(brr,brr+n);
        int flag=1;
        for(int i=0;i<n;++i)
        {
            if(brr[i]!=arr[i])
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            cout<<"0"<<endl;
        }
        else if(arr[0]==brr[0] || arr[n-1]==brr[n-1])
        {
            cout<<"1"<<endl;
        }else cout<<"2"<<endl;
    }
    return 0;
}