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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
#include <stack>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define MP make_pair
#define FOR(v,p,k) for(int v=(p);v<=(k);++v)
#define FORD(v,p,k) for(int v=(p);v>=(k);--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

#define ODD(x) ((x)%2)
#define EVEN(x) (!(ODD(x)))


int main() {
    int n;
    scanf("%d\n", &n);
    VI pos(n+1);
    REP(i, n) {
        int a;
        scanf("%d", &a);
        pos[a] = i;
    }
    int metric = 2 * n + 1;
    LL res = 1;
    if (n == 1) {
        printf("%d %lld\n", metric, res);
        return 0;
    }
    int req_all_from = n - 1;
    int old_req_all_from = n - 1;
    int left = min(pos[req_all_from], pos[n]);
    int right = max(pos[req_all_from], pos[n]);
    while (req_all_from >= 1) {
        FOR(a, req_all_from, old_req_all_from - 1) {
            left = min(pos[a], left);
            right = max(pos[a], right);
        }
 
        int x = right - left + 1;
        old_req_all_from = req_all_from;
        req_all_from = min(req_all_from, n - x / 2);
        if (req_all_from == old_req_all_from) {
            //res++;
            while ((req_all_from >= 1) && (left <= pos[req_all_from]) && (pos[req_all_from] <= right)) {
                req_all_from--;
            }
            if (req_all_from == 0) {
                res += ((LL)(n - 1 - right + 1)) * (left + 1);
            } else { 
                // max (max_diff) : n - (x+max_diff)/2 = req_all_from+1
                // 2* (n - (req_all_from +1)) = (x+max_diff)
                int max_diff = 2 * (n - (req_all_from + 1)) - x;
                if ((x + max_diff) % 2 == 0) {
                    max_diff++;
                }

                //int max_diff = 0;
                //while (( n - (max_diff + 1 +x) / 2) > req_all_from) {
                //    ++max_diff;
                //}

                if (pos[req_all_from] < left) {
                    int min_left = max(pos[req_all_from] + 1, left - max_diff);
                    FOR(i, min_left, left) {
                        int rest = max_diff - (left - i);
                        res +=  min(n - 1, right + rest) - right + 1;
                    }
                } else {
                    int max_rigth = min(pos[req_all_from] - 1, right + max_diff);
                    FOR(i, right, max_rigth) {
                        int rest = max_diff - (i - right);
                        res += left - max(0, left - rest) + 1;
                    }
 
                }
            }
        }

    }
    printf("%d %lld\n", metric, res);
    return 0;
}