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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>

#ifdef	DEBUG
#define	DBG(x)	(x)
#else
#define	DBG(x)
#endif

void dump(int *t, int n)
{
	int i;

	for (i = 0; i < n; i++)
		fprintf(stderr, " %d", t[i]);
}

int insert(int *t, int n, int x)
{
	int l = 0, r = n - 1;

	/*
	DBG(fprintf(stderr, "insert(%d):", x));
	DBG(dump(t, n));
	DBG(putc('\n', stderr));
	*/

	while (l <= r) {
		int i = (l + r) / 2;

		//DBG(fprintf(stderr, "\tinsert: n=%d x=%d l=%d r=%d t[%d]=%d\n", n, x, l, r, i, t[i]));

		if (x < t[i])
			r = i - 1;
		else
			l = i + 1;
	}

	//DBG(fprintf(stderr, "\tinsert: n=%d x=%d l=%d\n", n, x, l));

	if (l < n)
		memmove(t + l + 1, t + l, (n - l) * sizeof(*t));
	t[l] = x;

	/*
	DBG(fprintf(stderr, "insert[%d]:", l));
	DBG(dump(t, n + 1));
	DBG(putc('\n', stderr));
	*/
	return l;
}

inline int check(int *t, int n)
{
	div_t p = div(n, 2);
	p.rem = !p.rem;
	//DBG(fprintf(stderr, "\tcheck: n=%d t[%d]=%d t[%d]=%d\n", n, p.quot, t[p.quot], p.quot - p.rem, t[p.quot - p.rem]));
	return n + t[p.quot] + t[p.quot - p.rem];
}

int n;
int t[1000001];
int tl[1000001];
int tr[1000001];

int main(void)
{
	int i, imax, fmax, l, r, f;
	long long w = 0;

	scanf("%d", &n);
	fmax = 1 + 2 * n;
	for (i = 0; i < n; i++) {
		scanf("%d", &t[i]);
		if (t[i] == n)
			imax = i;
	}

	DBG(fprintf(stderr, "<%d>[%d] %d\n", imax, n, fmax));

	for (l = imax; l >= 0; l--) {
		insert(tl, imax - l, t[l]);
		f = check(tl, imax - l + 1);
		w += f == fmax;
		//DBG(fprintf(stderr, "%cL<%d,%d>[%d] %d %d\n", f == fmax ? '*' : ' ', l + 1, imax + 1, t[l], f, w));

		memcpy(tr, tl, (imax - l + 1) * sizeof(*tl));

		for (r = imax + 1; r < n; r++) {
			insert(tr, r - l, t[r]);
			f = check(tr, r - l + 1);
			w += f == fmax;

			//DBG(fprintf(stderr, "%cR<%d,%d>[%d] %d %d\n", f == fmax ? '*' : ' ', l + 1, r + 1, t[r], f, w));
		}
	}

	printf("%d %ld\n", fmax, w);
	return 0;
}