思路

理想状态下，题目要求放置一些堆盘子（废话），且对于第 $i$ 堆盘子，从上到下，是从小号到大号的（这样才能先洗小号）。并且，第 $i$ 堆盘子中号码最大的盘子的号码（即堆底盘子的号码）要小于第 $i+1$ 堆盘子中号码最小的盘子的号码（即堆顶盘子的号码）。

每个盘堆类似一个栈，于是我们可以开 $n$ 个 vector 来维护。对于第 $i$ 堆盘子，v[i].front() 是头部元素，也就是该堆盘子中号码最大的盘子的号码，而 v[i].back() 代表最小的号码。

为什么呢？因为 front 元素是这堆盘子里最先被 push_back 的，需要满足它是这堆里面号码最大的。

对于放入编号为 $k$ 的盘子，二分求出合适它的盘堆，再一一判断插入的位置。如果 $k$ 大于已经洗干净的盘子中编号最大的盘子，那么 $k$ 就放不了了。

注意

题目输出中的小号在下，大号在上的意思是先洗干净小号盘，在洗干净大号盘。

时间复杂度 $O(n \log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int Max=1e5+10;
int n,nxt,maxx;
//nxt表示盘堆的数量，即最右侧盘堆的编号
//maxx记录已经取出（洗干净）的盘子中号码最大的盘子 
vector<int> v[Max]; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) {
		int k;cin>>k;
		//若没有盘堆，加一个盘堆 
		if(!nxt)v[++nxt].push_back(k);
		else{
			//若该盘子已经不能按顺序洗了
			if(k<maxx) { 
				cout<<i-1;
				return 0;
			}
			//放入新的一堆
			if(v[nxt].front()<k) { 
				v[++nxt].push_back(k);
				continue; 
			}
			//二分插入在哪一堆里 
			int ans,L=1,R=nxt;
			while(L<=R) {
				int mid=(L+R)>>1;
				if(v[mid].front()>k)R=mid-1,ans=mid;
				else L=mid+1;
			}
			//枚举插入在该堆的哪一位置
			//如要插入，就必须把上方小号的盘子洗干净
			//即pop_back掉 
			while(!v[ans].empty()&&v[ans].back()<k) {
				maxx=max(maxx,v[ans].back());
				v[ans].pop_back(); 
			}
			v[ans].push_back(k);
		}
	}
	//最理想状态 
	cout<<n;
	return 0;
}