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
#include <bits/stdc++.h>
using namespace std;
int n,maxa,wyn,l,r,a;
double y;
int tab[1000005];
bool prawo[1000005];
vector<int> vec;

int outside()
{
	l=0;
	r=0;	
	for(int i = 0;i<maxa;i++)
	{
		if(tab[i]<y){
			l++;
		} else {
			break;
		}
	}
	for(int i = n;i>maxa;i--)
	{
		if(tab[i]<y){
			r++;
		} else {
			break;
		}
	}
	if(l==0){
		l++;
	}
	if(r==0){
		r++;
	}
	return(l*r);
	
	
	
}






int main() {
	ios_base::sync_with_stdio(false);
	cin>>n;
	y=n+1;
	y/=2;
	wyn = 1;
	cout<<2*n+1<<' ';
	if(n==1){
		cout<<1;
		return(0);
	}
	for(int i = 0;i<n;i++){
		cin>>tab[i];
		if(tab[i]==n)
		{
			maxa=i;
		}
		if(maxa)
		{
			prawo[tab[i]]=true;
		}
		vec.push_back(tab[i]);
	}
	int ii = n;
	int iii = 0;
	while(vec.size()>1){
	
	wyn+=outside();
	vec.erase(vec.begin(),vec.begin()+l);
	vec.erase(vec.end()-r,vec.end());
	sort(vec.begin(),vec.end());
	a=vec[0];

	if(prawo[a])
		{
			
			while(vec[0]==a)
			{
				if(tab[ii]<a)
				{
					ii--;
				}
				else
				{
					vec.erase(vec.begin()+tab[ii]-a-1);
					ii--;
				}
			}
		}
		else
		{
					while(vec[0]==a)
			{
				if(tab[iii]<a)
				{
					iii++;
				}
				else
				{
					vec.erase(vec.begin()+tab[iii]-a-1);
					iii++;
				}
			}

		}
		wyn++;
		if(vec.size()%2==0)
		{
			y=(vec[vec.size()/2+1]+vec[vec.size()/2])/2;
			
		} else
		{
			y=vec[(vec.size()+1)/2];
		}
		
	}
	cout<<wyn+1;
	return(0);
}