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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
// C4 - Ranking sklepow internetowych
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getMinRemovedFromOtherSide(int val, int pos, int n) {
	int median;
	if (n % 2) {
		median = (n + 1) / 2;
		if (val < median) {
			return 0;
		}
		return max(2 * (val - median) - pos + 1, 0);
	} else {
		median = n / 2 + 1;
		if (val < median) {
			return 0;
		}
		return max(0, 2 * (val - median) - pos + 2);
	}		
}

int main() {
	int n, a, l, r;
	long long result;
	vector<int> ratings;
	vector<int> leftValues;
	vector<int> rightValues;
	vector<int> leftReaches;
	vector<int> rightReaches;
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		ratings.push_back(a);
	}

	for (int i = 0; i < n; ++i) {
		leftValues.push_back(ratings[i]);
		rightValues.push_back(ratings[n - 1 - i]);
	}
	
	for (int i = 1; i < n; ++i) {
		leftValues[i] = max(leftValues[i], leftValues[i - 1]);
		rightValues[i] = max(rightValues[i], rightValues[i - 1]);
	}
	
	for (int i = 0; i < n; ++i) {
		leftReaches.push_back(getMinRemovedFromOtherSide(leftValues[i], i, n));
		rightReaches.push_back(getMinRemovedFromOtherSide(rightValues[i], i, n));
	}	
	
	result = 0;
	for (l = 0; l < n; ++l) {
		if (l == 0) {
			r = 0;
		} else {
			r = leftReaches[l - 1];
		}
		while (l + r < n) {
			if (r == 0 || rightReaches[r - 1] <= l) {
				++result;
//				cout << "res " << l << " " << r << endl;
				++r;
			} else {
				r += rightReaches[r - 1] - l;
			}
		}
	}
	
	cout << 2 * n + 1 << " " << result;
	
/*	cout << endl;
	for (int i = 0; i < n; ++i) {
		cout << leftValues[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < n; ++i) {
		cout << rightValues[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < n; ++i) {
		cout << leftReaches[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < n; ++i) {
		cout << rightReaches[i] << " ";
	}
	cout << endl;*/
	
	
	/*cout << "TEST" << endl;	
	for (int i = 1; i <= n; ++i) {
		cout << getMinRemovedFromOtherSide(i, 0, n) << " ";
	}*/
	
	
	return 0;
}