记录编号	605131	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3924.排列变换	最终得分	100
用户昵称	AeeE5x	是否通过	通过
代码语言	C++	运行时间	5.066 s
提交时间	2025-08-14 14:41:26	内存使用	15.96 MiB

//#include<bits/stdc++.h>
//#include<owni/usefs.h>
#include<iostream>
#define inf 0x3f3f3f3f
#define lb(x) (x&(-x))
using namespace std;

struct node{
	int l,r;
	int val_max;
	int lz_add;
}t[4000010];

void pushdown(int p){
	t[p<<1].val_max+=t[p].lz_add;
	t[p<<1|1].val_max+=t[p].lz_add;
	
	t[p<<1].lz_add+=t[p].lz_add;
	t[p<<1|1].lz_add+=t[p].lz_add;
	
	t[p].lz_add=0;
}

void pushup(int p){
	t[p].val_max=max(t[p<<1].val_max,t[p<<1|1].val_max);
}

void build(int l,int r,int p=1){
	t[p].l=l;
	t[p].r=r;
	t[p].lz_add=0;
	t[p].val_max=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
}

void change(int l,int r,int p=1){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].lz_add++;
		t[p].val_max++;
	}else{
		pushdown(p);
		int mid=t[p].l+t[p].r>>1;
		if(l<=mid) change(l,r,p<<1);
		if(r>mid) change(l,r,p<<1|1);
		pushup(p);
	}
}

int query(int x,int p=1){
	if(t[p].l==t[p].r) return t[p].val_max;
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) return query(x,p<<1);
	else return query(x,p<<1|1);
}

int n;
int ls[1000010];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("permutrans.in","r",stdin);
	freopen("permutrans.out","w",stdout);
//	freopen("tss/A/ex_mine8.in","r",stdin);
//	freopen("tss/A/mine.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>ls[i];
	
	build(1,n);
	for(int i=1;i<=n;i++){
		if(i<=ls[i]){
			if(1<=ls[i]-i+1) change(1,ls[i]-i+1);
			if(n+2-i<=n) change(n+2-i,n);
		}else{
			change(n-i+2,n-i+1+ls[i]);
		}
	}
	
	int ind=0,mx=0;
	for(int i=1;i<=n;i++){
		int w=query(i);
		if(w>mx) mx=w,ind=i;
	}
	cout<<mx<<" "<<ind-1;
	
	return 0;
}