树状数组
1：把n个数字放在一个m+i位置开始，每当一个位置移动在最前面，旧位置为0，新位置为1，每次更新一下max，也就是前缀和==有多少个数字，m次查询跑完了，再更新一次
#include<bits/stdc++.h>
//typedef long long ll;
//#define ull unsigned long long
//#define int long long
#define F first
#define S second
#define endl "\n"<<flush
#define lowbit(x) (x&(-x))
#define ferma(a,b) pow(a,b-2)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int MAXN=0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
void file()
{
#ifdef ONLINE_JUDGE
#elsefreopen("cin.txt","r",stdin);// freopen("cout.txt","w",stdout);
#endif
}
const int N=1e6+5;
pair<int,int>ans[N];
int c[N];
void modify(int pos,int value)
{while(pos<N)c[pos]+=value,pos+=lowbit(pos);
}
int query(int pos)
{int ans=0;while(pos)ans+=c[pos],pos-=lowbit(pos);return ans;
}
signed main()
{IOS;//file();int n,m;cin>>n>>m;map<int,int>ma;for(int i=1; i<=n; i++)modify(m+i,1),ma[i]=m+i,ans[i].F=ans[i].S=i;for(int i=0;i<m;i++){int x;cin>>x;ans[x].F=min(ans[x].F,1);ans[x].S=max(ans[x].S,query(ma[x]));modify(ma[x],-1);modify(m-i,1);ma[x]=m-i;}for(int i=1; i<=n; i++)ans[i].S=max(ans[i].S,query(ma[i]));for(int i=1; i<=n; i++){cout<<ans[i].F<<" "<<ans[i].S<<endl;}return 0;
}