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
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;



int main(){
	long long n, index, ways;
	bool all_covered = false;
	cin >> n;
	vector<long long> reviews(n);
	// cout << "| ";
	for (int i = 0; i < n; i ++){
		cin >> index;
		reviews[n - index] = i;
		// cout << index << " | "; 
	}
	// cout << endl << endl;
	long long range_begin = reviews[0];
	long long range_end = reviews[0];
	// cout << "i\tk\tw\tb\te\tr\tcs" << endl;
	ways = 1;
	for(int i = 1; i < n && !all_covered; i ++){
		range_begin = min(range_begin, reviews[i]);
		range_end = max(range_end, reviews[i]);
		long long core_size = range_end - range_begin + 1;

		if(core_size <= 2*i){
			long long diff = max(0LL,2*i-core_size);
			long long temp_beg = max(0LL, range_begin - diff);
			long long temp_end = min(n-1, range_end + diff);
			long long range = temp_end - temp_beg + 1;
			if(range == 2*i) {
				ways += 1;
				// cout << i << "\t" << 2*i << "\t" << 1 << "\t" << temp_beg << "\t" << temp_end << "\t" << range << "\t" << core_size <<endl;
			}
			else {
				// cout << i << "\t" << 2*i << "\t" << range - 2*i + 1<< "\t" << temp_beg << "\t" << temp_end << "\t" << range << "\t" << core_size <<endl;
				ways += range - 2*i + 1;
			}
			all_covered = 2*i == n;
		}
		//else // cout << i << "\t" << 2*i << "\t" << 0 << "\t" << range_begin << "\t" << range_end << "\t" << "-" << "\t" << core_size << endl;
		
		if(!all_covered){
			if(core_size <= 2*i+1){
				long long diff = max(0LL,2*i + 1 - core_size);
				long long temp_beg = max(0LL, range_begin - diff);
				long long temp_end = min(n-1, range_end + diff);
				long long range = temp_end - temp_beg + 1;
				if(range == 2*i+1) {
					ways += 1;
					// cout << i << "\t" << 2*i+1 << "\t" << 1 << "\t" << range_begin << "\t" << range_end << "\t" << range << "\t" << core_size <<endl;
				}
				else {
					// cout << i << "\t" << 2*i+1 << "\t" << range - 2*i + 1 << "\t" << temp_beg << "\t" << temp_end << "\t" << range << "\t" << core_size <<endl;			
					ways += range - 2*i;
				}
				all_covered = 2*i + 1 == n;
			}
			//else // cout << i << "\t" << 2*i+1 << "\t" << 0 << "\t" << range_begin << "\t" << range_end << "\t" << "-" << "\t" << core_size << endl;
		}
	} 
	cout << 2*n +1 << " " << ways;

}