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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <vector>
#include <queue>

int min(int a, int b){
	return a < b ? a : b;
}

int min(int a, int b, int c, int d){
	return min(min(a,b),min(c,d));
}

int max(int a, int b){
	return a > b ? a : b;
}

int checkScore(int n, int lastMed, int total){
	int liczbaWiekszych = (n - lastMed + 1);
	return liczbaWiekszych > total / 2;//jesli jest nieparzysta to musi byc wieksza czyli 3 z 5ciu, jesli parzysta to np. 3 z 4
}

int ileMoznaDodac(int n, int lastMed, int total){
	int liczbaWiekszych = (n - lastMed + 1);
	int liczbaMniejszych = total - liczbaWiekszych;
//	printf("ileMoznaDodac %d %d\n", liczbaWiekszych , liczbaMniejszych);
	return min(liczbaWiekszych - liczbaMniejszych - 1, n - total);
}

//std::vector<int> visitedValues(1000001, 0);
int visitedValues[1000001] = {0};
int values[1000001] = {0};
int positions[1000001] = {0};

int main(){
	int n;
	scanf("%d", &n);
//	std::vector<int> values(n);
//	std::vector<int> positions(n + 1);
	for(int i = 0; i < n; ++i){
		scanf("%d", &values[i]);
		positions[values[i]] = i;
	}
	int b = positions[n];
	int e = b;
	int lastMedValue = n;
	long long int totalSpaces = 1;
	int SCORE_VAL = n * 2 + 1;
//	printf("PRZEDZIALY %lld granice %d %d\n", totalSpaces, b, e);
//	std::priority_queue<int> newValues;
	while(0 < b || e < n - 1){// lastValue > 1
		int nextVal = lastMedValue - 1;
		int idx = positions[nextVal];
//		printf("===> wartosc:%d  pozycja:%d\n", nextVal, idx);

		if (idx < b){
//			printf("SZUKAM <<<\n");
			for(int i  = b - 1; i >= idx ;--i){
//				newValues.push(values[i]);
				visitedValues[values[i]] = 1;
			}
			b = idx;

		} else if (idx > e){
//			printf("SZUKAM >>>\n");
			for(int i = e + 1; i <= idx ;++i){
//				printf("%d ---\n", values[i]);
//				newValues.push(values[i]);
				visitedValues[values[i]] = 1;
			}
			e = idx;
		}
//		printf("===== %d %d\n",newValues.top(), nextVal);
//		while(!newValues.empty() && newValues.top() == nextVal){
////			printf("===== %d %d\n",newValues.top(), nextVal);
//			lastMedValue = nextVal;
//			newValues.pop();
//			--nextVal;
//		}

//		printf("===== %d %d\n",newValues.top(), nextVal);
//		while(!newValues.empty() && newValues.top() == nextVal){
		while(visitedValues[nextVal] == 1){
//			printf("===== %d %d\n",newValues.top(), nextVal);
			lastMedValue = nextVal;
			--nextVal;
		}


		int dlugoscPrzedzialu = e - b + 1;
		int wolne = ileMoznaDodac(n, lastMedValue, dlugoscPrzedzialu);

//		printf("WARTOSC MED %d  WSZYSTKIE %d, WOLNE %d\n", lastMedValue, dlugoscPrzedzialu, wolne);


		if (wolne >= 0){
			int lewa = 0;
			int prawa = 0;
			int nextValPos = positions[lastMedValue - 1];//tego musimy ominac

			if (nextValPos < b) lewa = b - nextValPos - 1;
			else lewa = b;
			if (e < nextValPos) prawa = nextValPos - e - 1;
			else prawa = n - e - 1;


			lewa = min(lewa, wolne);
			prawa = min(prawa, wolne);
			long long int wszystiePasujace = (lewa + 1) * (prawa + 1);
			int maxDlugosc = lewa + prawa + dlugoscPrzedzialu;
			int dlugoscAkceptowalna = min(maxDlugosc, wolne + dlugoscPrzedzialu);
			int roznica = maxDlugosc - dlugoscAkceptowalna - 1;
			long long int doOdjecia = ((roznica + 1) * (roznica + 2)) / 2;
			totalSpaces += (wszystiePasujace - doOdjecia);


//			printf("LEWA %d  PRAWA %d,  wszystkie:%lld roznica:%d (%d %d) doOdjecia:%lld\n", lewa, prawa, wszystiePasujace, roznica, maxDlugosc, dlugoscAkceptowalna, doOdjecia);
//			printf("PRZEDZIALY %lld granice %d %d\n", totalSpaces, b, e);

/*
			long long int dodatkowePrzedzialy = 0;
			for(int diff = 0; diff <= wolne; diff++){
				int dodatkowy = max(0,min(lewa + prawa + 1 - diff, lewa + 1, prawa + 1, diff + 1));
//				printf("diff %d %d %d %d dodatkowy:%d\n", diff + 1, lewa + prawa + 1 - diff, lewa + 1, prawa + 1, dodatkowy);
				dodatkowePrzedzialy += dodatkowy;
				if (dodatkowy == 0) break;
			}


//			printf("RUCH lewa %d prawa %d  \n", lewa, prawa);
			totalSpaces += dodatkowePrzedzialy;*/
		}



	}

	printf("%d %lld\n",SCORE_VAL, totalSpaces);
	return 0;
}