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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
using namespace std;

#define LL long long

LL tab[1000100];

LL funcel[1000][1000];

LL med2(int i, int j)
{
	set<LL>s(tab+i,tab+j+1);
	auto it = s.begin();
	int l=(j-i+1)/2;
	while(l--)it++;
	if((j-i+1)%2==1)return *it * 2;
	else 
	{
		LL p=*it;
		it--;
		return (*it + p);
	}
}

LL policz(int i, int j)
{
	if(i>j)return 0;
	return med2(i,j)+j-i+1;
}

int findmax(LL n)
{
	int maxi = -1;
	LL max = 0;
	for (int i =0;i<n;i++)
	{
		if(tab[i]>max) {max=tab[i];maxi=i;}
	}
	return maxi;
}

set<pair<int,int>>odwiedzone;
LL ile=0;
LL cel=0;
LL n;

void rek(int i, int j)
{
	if(odwiedzone.find(make_pair(i,j))!=odwiedzone.end()) return;
	odwiedzone.insert(make_pair(i,j));
	LL p = policz(i,j);
	if (p!=cel)return;
	ile++;
	if(i>0)rek(i-1,j);
	if(j<n-1)rek(i,j+1);
	if(i!=j)
	{
		rek(i+1,j);
		rek(i,j-1);
	}
}

void alg()
{
	cel = policz(0,n-1);
	int i = findmax(n);
	rek(i,i);
	rek(0,n-1);
	printf("%lld %lld\n",cel,ile);
}


int main() {
	// your code goes here
	scanf("%lld",&n);
	for(int i = 0; i<n;i++)
	{
		scanf("%lld",tab+i);
	}
	
/*	
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			funcel[i][j]=policz(i,j);
		}
	}

	printf(" ");
	for(int i=0;i<n;i++)printf("   %d",i);
	printf("\n");

	for(int i=0;i<n;i++)
	{
		printf("%d ",i);
		for(int j=0;j<n;j++)
		{
			funcel[i][j]=policz(i,j);
			printf("%3lld ",funcel[i][j]);
		}
		printf("\n");
	}
*/
	alg();
	
	return 0;
}