#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	std::cin >> n;
	VI A(n);
	FOR(i, n) std::cin >> A[i], A[i]--;

	std::cout << 2*n+1 << " ";

	VI pos(n);
	FOR(i, n) pos[A[i]] = i;

	int mn = pos[n-1];
	int mx = pos[n-1];
	ll ans = 1;

	REP(i, 2, n / 2 + 2){
		int p = pos[n-i];
		mn = std::min(mn, p);
		mx = std::max(mx, p);
		int len = mx - mn + 1;

		int rl = (i-1)*2;
		int more = rl - len;
		// std::cout << "len " << len << " rl " << rl << std::endl;
		if(more >= 0){
			int ways = std::min(mn, more) + std::min(n-1-mx, more) - more + 1;
			ans += ways;
			// std::cout << "len " << len << " rl " << rl << " ways " << ways << std::endl;

		}

		rl = (i-1)*2+1;
		more = rl - len;
		// std::cout << "len " << len << " rl " << rl << std::endl;
		if(rl <= n && more >= 0){
			int ways = std::min(mn, more) + std::min(n-1-mx, more) - more + 1;
			ans += ways;
			// std::cout << "len " << len << " rl " << rl << " ways " << ways << std::endl;
		}

	}

	std::cout << ans << "\n";

	return 0;
}