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
#include <bits/stdc++.h>
using namespace std;
const int L=1<<20;
int d[2][L<<1];
void upd(int w, int c)
{
	w+=L-1;
	d[0][w]=d[1][w]=c;
	w>>=1;
	while (w)
	{
		d[0][w]=min(d[0][w], c);
		d[1][w]=max(d[1][w], c);
		w>>=1;
	}
	return;
}
int query(int p, int k, bool kt)
{
	p+=L-1;
	k+=L-1;
	int r=(kt? INT_MIN : INT_MAX);
	while (p <= k)
	{
		if (p&1)
		{
			if (kt)	r=max(r, d[1][p]);
			else 	r=min(r, d[0][p]);
		}
		if (!(k&1))
		{
			if (kt)	r=max(r, d[1][k]);
			else 	r=min(r, d[0][k]);
		}
		p=(p+1)>>1;
		k=(k-1)>>1;
	}
	return r;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;	cin>>n;
	memset(d[0], 0x3f, sizeof(d[0]));
	for (int i=1; i<=n; i++)
	{
		int a;	cin>>a;
		upd(a, i);
	}
	long long odp=0;
	for (int i=1; i<=n; i++)
	{
		int m=(2*n+1-i)/2;
		int p=query(m, n, 0), k=query(m, n, 1);
//		cout<<i<<" "<<m<<" "<<p<<" "<<k<<" ";
		odp+=max(0, min(p, n-i+1)-max(1, (k-i+1))+1);
//		cout<<odp<<"\n";
	}
	cout<<2*n+1<<" "<<odp;
	return 0;
}
/*
5
1 4 3 5 2
*/