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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
//#undef _HOME_
#ifdef _HOME_
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define RESULT(x) {cout<<(x);return 0;}

const int MAX_N = 1000002;
int tab[MAX_N];
int pos[MAX_N];
int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin>>n;
	REP(x,n) {
		cin>>tab[x];
		pos[tab[x]]=x;
	}
	const int top = pos[n];
	int mini=top, maxi=top;
	long long result = 0;
	for(int i=0;i<n;++i) {
		// we get [n] and [i] different numbers
		// but we must always have all in range [n-median..n]
		mini = min(mini, pos[n-(i+1)/2]);
		maxi = max(maxi, pos[n-(i+1)/2]);
		DEBUG(cerr<<"range is ["<<mini<<","<<maxi<<"]"<<endl;)
		mini = min(mini, n-1-i);
		maxi = max(maxi, i);
		DEBUG(cerr<<"real range is ["<<mini<<","<<maxi<<"]"<<endl;)
		if (maxi-mini <= i) {
			int length = maxi-mini;
			int unused = i-length;
			DEBUG(cerr<<"length: "<<length<<", unused: "<<unused<<endl;)
			result += 1+min(min(mini, n-1-maxi),unused);
			DEBUG(cerr<<result<<" -> result += 1+min("<<mini<<", "<<(n-1-maxi)<<","<<unused<<")"<<endl;)
		}
		DEBUG(else cerr<<result<<" - cannot match"<<endl;)
	}

	cout<<(n+n+1)<<" "<<result;
	return 0;
}