题目描述

序列 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;
//		int t=99999;
//		for(int j=i+1;j<=n;j++){
//			int l=i,r=j;
//			while(l<=r){
//				int mid=(l+r)/2;
//				if(a[mid]<t){
//					t=a[mid];
//					l=mid+1;
//				}else{
//					r=mid-1;
//				}
//			}
//		}
//		if(t<a[i]) continue;
//		ans++;
//	}
//	cout<<ans;
//	return 0;
//}
#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;
}