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
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
long long a[1000006],b[1000006];
long long n,pr,le,it,g,po,pom;
long long maks,ilosc,mi,ma,o;
stack<pair<int,int> >s;
bool opusc[1000006];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
	cin>>a[i];
	b[a[i]] = i;
	opusc[i] = false;
}

maks = 2 * n + 1;
ma = 0;
mi = n + 1;
ilosc = 0;
o = 1;
for(int i=n;i>=1;i--)
{	
	if(ma >= 1)
	{
		for(int j=ma + 1;j<b[i];j++)
			opusc[a[j]] = true;
	}
	if(mi <= n)
	{
		for(int j=mi - 1;j>b[i];j--)
			opusc[a[j]] = true;
	}
	ma = max(ma,b[i]);
	mi = min(mi,b[i]);
	if(opusc[i - 1] || ma - mi > 2 * (n - i))
	{
		continue;
	}
	if(i > 1)
		it = b[i - 1];
	
	pr = 2 * (n - i) + mi;
	le = ma - 2 * (n - i);
	pr = min(pr,n);
	le = max(le,o);
	//cout<<it<<endl;
	if(it < mi || ma < it)
	{
		
		if(it > ma)
			pr = min(pr,it - 1);
		else if(it < mi)
			le = max(le,it + 1);
		
	}
		
	pr = pr - ma;
	le = mi - le;
	g = 2 * (n - i) - ma + mi;
	
	if(g - le >= pr)
		pom = (le + 1) * (pr + 1);
	else
	{
		po = g - pr + 1;
		pom = (po) * (pr + 1);

		pom += (le - po + 1) * (2 * g - le - po + 2) / 2;
	}
	//cout<<i<<" "<<pom<<" "<<le<<" "<<pr<<" "<<g<<"\n";
	ilosc += pom;
}

cout<<maks<<" "<<ilosc<<"\n";

	
return 0;	
}