1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define int long long
#define ll long long

#define BE(x) x.begin(),x.end()
#define EB(x) x.end(),x.begin()

#define st first
#define nd second
using namespace std;

int foo(int a, int x){
	
int sum=0;
	for(int i=0;i<=x;i++) sum+= min(a,x);
	return sum;
}

int foo2(int a,int x){
	if(x>=a)return a*(a+1)/2+(x-a)*a;
	return x*(x+1)/2;
}
int goo(int a, int b, int x){
	int sum=0;
//	for(int l=0;l<=x;l++) sum+=min(l,a)+min(l,b)+1-l;
	sum = foo2(a,x)+foo2(b,x)+(x+1)-(x+1)*x/2;
	return sum;
	
}

int32_t main(){

	ios::sync_with_stdio(false); cin.tie(NULL);
	int n;cin>>n;
	vector<int> V(n);
	//for(auto&x:V) cin>>x;
	for(int i=0;i<n;i++){
		int w;cin>>w;V[i]=w;
	}
	vector<int> where(n+1);
	for(int i=0;i<n;i++) where[V[i]]=i;
	
	int L=where[n], R=where[n];
	int res=0;
	
	for(int i=n;i>=1;i--){
		L=min(L,where[i]);
		R=max(R,where[i]);
		if(i>1){
			int j=where[i-1];
			if(L<=j&&j<=R) continue;
			int a=L, b=n-R-1;
			if(R<j) b=j-R-1;
			if(j<L) a=L-j-1;
			int x=2*(n-i+1)-R+L-2;
			int s=-100;
			//	cout<<i<<":   a:"<<a<<", b:"<<b<<", x:"<<x<<", s:";
				x = min(x, a+b);
		//	s=foo(a,x)+foo(b,x)+(x+1) -x*(x+1)/2;
				s=goo(a,b,x);
		//		cout<<s<<endl;
				if(x>=0) res+=s;
		
		}
	}
	
	cout << 2*n+1<<" "<<res+1<<endl;
 
}