题目描述

序列 O(n) 分区算法将一个数组 A 围绕一个枢轴元素 pivot（ pivot 是 A 的一个元素）分成三部分： 包含小于等于枢轴元素的左子序列、枢轴本身，以及包含大于枢轴元素的右子序列。

分区算法是流行的排序算法 Quicksort 的一个组成部分。 通常， pivot 的选择是随机的，因此 Quicksort 的预期运行时间为 O(nlogn) 。

现在有一个问题是这样的： 一个有 n 个整数的数组 A ，我们用 A 中的一个整数作为 pivot 对 A 进行分割，得到一个变换后的数组 A ​∗ ​​ 。 给定这个变换后的数组 A ​∗ ​​ ，你需要计算有多少个整数可能作为了所选的 pivot。

输入

第一行包含一个整数 n ( 3 ≤ n ≤ 1 0^ 5 ) n(3≤n≤10 ​^5 ​​ )。 第二行包含 n 个整数 a i

( 1 ≤ a i ≤ 1 0^9 ) a i a ​i ​​ 互不相同，用于描述转换后的数组 A ​∗ ​​ 。

#include<bits/stdc++.h>
using namespace std;
int n,a[100000],ans,b[100000];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	b[1]=a[1];
	for(int i=1;i<=n;i++)b[i]=max(b[i-1],a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]<b[i]) continue;
		bool f=true;
		for(int j=i+1;j<=n;j++){
			if(a[j]<=a[i]){
				f=false;
				break;
			}
		}
		if(f) ans++;
	}
	cout<<ans;
	return 0;
}

请问老师们我该如何改进时间复杂度？（玄关）