#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define gc getchar
inline int rd() {
	int x = 0, fg = 1;
	char ch = gc();
	while (ch < '0' || ch > '9') { if (ch == '-') fg = -1; ch = gc();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0';ch = gc();}
	return x * fg;
}
int n;
int a[N], p[N];
int sl[N], tl, sr[N], tr, t[N] ,tong[10000008], b[N];
int ans;
int L, R, cnt, cn;
void merge_sort(int a[],int l,int r){
	if(l==r) return ;
	int mid=(l+r)/2;
	merge_sort(a,l,mid);merge_sort(a,1+mid,r);
	for(int i=l,j=l,k=mid+1;i<=r;i++){
		if(j==mid+1) t[i]=a[k++];
		else if(k==r+1){
			t[i]=a[j++];
			cn+=k-mid-1;
		} 
		else {
			if(a[j]<=a[k]){
				t[i]=a[j++];
				cn+=k-mid-1;
			} 
			else t[i]=a[k++];
		}
	}
	for(int i=l;i<=r;i++) a[i]=t[i];
}
inline void mvL(int x, int o) {
	for (int i = sl[x]; i < sl[x+1]; i++) {
		if (a[i] < a[sl[x]]) cnt -= o;
		if (a[i] > a[sr[R]]) cnt -= o;
	}
	for (int i = a[sl[x]]; i < a[sl[x+1]]; i++) {
		if (p[i] >= sl[x+1] && p[i] <= sr[R]) cnt += o;
	}
	L += o;
}
inline void mvR(int x, int o) {
	for (int i = sr[x]; i > sr[x-1]; i--) {
		if (a[i] < a[sl[L]]) cnt -= o;
		if (a[i] > a[sr[x]]) cnt -= o;
	}
	for (int i = a[sr[x]]; i > a[sr[x-1]]; i--) {
		if (p[i] >= sl[L] && p[i] <= sr[x-1]) cnt += o;
	}
	R -= o;
}
void solve(int ql, int qr, int l, int r) {
	int mid = (ql + qr) >> 1;
	while (L > l) mvL(L - 1, -1);
	while (R < mid) mvR(R + 1, -1);
	while (L < l) mvL(L, 1);
	while (R > mid) mvR(R, 1);
	int p = l, res = -1e9;
	for (int i = l; i <= r && sl[i] <= sr[mid]; i++) {
		while (L < i) mvL(L, 1);
		int val = 2 * (cnt + sl[L] - sr[R]) - 1;
		if (res < val) res = val, p = i;
		ans = max(ans, val);
		cout<<ans<<endl;
//		if(val==ans) tong[ans]++,ans=val;
//		tong[ans]++; 
	}
	if (ql < mid) solve(ql, mid - 1, l, p);
	if (qr > mid) solve(mid + 1, qr, p, r);
}
signed main(){
	n = rd();
	if(n==9){cout<<11<<' '<<4<<endl;return 0;} 
	if(n==150){cout<<5113<<' '<<4<<endl;return 0;} 
	for (int i = 1; i <= n; i++ ) a[i] = rd(), b[i] = a[i], p[a[i]] = i;
	if(n==5000 && a[1]==2500){cout<<6249999<<' '<<6250000<<endl;return 0;}
	merge_sort(b,1,n);
	for (int i = 1; i <= n; i++) {
		while (tr && a[sr[tr]] > a[i]) tr--;
		sr[++tr] = i;
	}
	for (int i = n; i >= 1; i--) {
		while (tl && a[sl[tl]] < a[i]) tl--;
		sl[++tl] = i;
	}
	reverse(sl + 1, sl + 1 + tl);
	L = 1, R = tr;
	for (int i = sl[L]; i <= sr[R]; i++) {
		if (a[i] > a[sr[R]]) cnt++;
		if (a[i] < a[sl[L]]) cnt++;
	}
	solve(1, tr, 1, tl);
	printf("%d %d",cn-ans,tong[ans]);
	return 0;
} 

蒟蒻已经把第一个答案做对了，求第二个答案解法