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
#include <algorithm>
#include <cstdio>

using namespace std;

int inp[2000000], loc[2000000];
bool inSet[2000000];

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &inp[i]);
		loc[inp[i]] = i;
		inSet[inp[i]] = false;
	}
	long long res = 1;
	int left = loc[n], right = loc[n], len = 2;
	inSet[n] = true;

	while (len <=n)
	{
		int cur = n - (len)/2;
		
		int next = loc[cur];
		
		if (!inSet[cur])
		{
			if (next < left)
			{
				for (int i = next; i < left; i++)
				{
					inSet[inp[i]] = true;
				}
				left = next;
			}
			else
			{
				for (int i = right+1; i <= next; i++)
				{
					inSet[inp[i]] = true;
				}
				right = next;
			}

		}
		
		if (len >=right-left+1)
		{
			int mi = max(0, right-len+1), ma = min(left+len-1, n-1 );
			res += (long long) (ma-mi-len+2);
		}
		len++;
	}
	
	printf("%d %lld", 2*n+1,  res);

	

	return 0;
}