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
#include <bits/stdc++.h>

using namespace std;
#define LL long long
#define BIGMOD 1000000007LL

#define DBG(X) 

int score(const vector<int> &x)
{
    if (x.size() % 2 == 1)
    {
        return 2* x[x.size() / 2] + x.size();
    }
    else
    {
        int m = x.size() / 2;
        return x[m] + x[m-1] + x.size();
    }
    return 0;
}

pair<LL,LL> solveBrut(const vector<int> &v)
{
    int n = v.size();
    LL bestScore = 2*n+1;
    LL numberOfWays = 0;
    for (int i=0; i < n; i++)
      for (int j=i; j < n; j++)
      {
          vector<int> x;
          for (int k=i; k<=j; k++) x.push_back(v[k]);
          sort(x.begin(), x.end());
          if (score(x) == bestScore) {
              numberOfWays++;
              //printf("%d %d\n", i,j);
          } 
      }
    return make_pair(bestScore, numberOfWays);
}

bool isInside(const pair<int,int> &a, int x)
{
    if (x >= a.first && x <= a.second) return true;
    if (x == (a.second+1) || x == (a.first-1)) return true;
    return false;
}

pair<int,int> merge(const pair<int,int> &a, int x)
{
    return make_pair(min(a.first, x), max(a.second, x));
}

int length(const pair<int,int> &a)
{
    return a.second - a.first + 1;
}

pair<LL,LL> solveFast(const vector<int> &v)
{
    int n = v.size();
    LL bestScore = 2 * n + 1;
    LL numberOfWays = 0;
    if (n==1) return make_pair(3,1);
    if (n==2) return make_pair(5,2);

    vector<pair<int, int> > vs;
    for (int i=0; i < n; i++)
    {
        vs.emplace_back(make_pair(v[i], i));
    }
    sort(vs.begin(), vs.end()); //reverse(vs.begin(), vs.end());

    pair<int,int> interval(vs[n-1].second, vs[n-1].second);
    numberOfWays++;

    for (int i=n-2; i>=0; i--)
    {
        int pos = vs[i].second;
        int val = vs[i].first;
        
        // nieparzyste
        {
            int requiredLength = 2*(n-val)+1;
            DBG(printf("processing odd value %d at pos %d. Required length=%d Interval:(%d,%d)\n", val, pos, requiredLength, interval.first, interval.second));
            pair<int,int> newInterval = merge(interval, pos);
            if (requiredLength <= n && length(newInterval) <= requiredLength)
            {
                pair<int,int> boundaries = make_pair(max(0, newInterval.second - requiredLength + 1), min(n-1, newInterval.first + requiredLength - 1));

                int solutionsHere =  length(boundaries) - requiredLength + 1;
                DBG(printf("odd boundaries (%d,%d)\n",boundaries.first, boundaries.second));
                numberOfWays += solutionsHere;
                DBG(printf("-> found a odd way at val=%d, pos=%d, newInterval=(%d,%d), diff=%d, solutionsHere=%d\n",
                 val, pos, newInterval.first, newInterval.second, solutionsHere));
            }

        }
        // parzyste
        {
            int pos2 = vs[i+1].second;
            int val2 = vs[i+1].first;
            int requiredLength = 2*(n-val);
            DBG(printf("processing even values %d,%d at pos %d,%d. Required length=%d Interval:(%d,%d)\n", val, val2, pos, pos2, requiredLength, interval.first, interval.second));

            // TODO: Check pos and pos2 together!
            pair<int,int> newInterval = merge(merge(interval, pos), pos2);
            if (requiredLength <= n && length(newInterval) <= requiredLength)
            {
                pair<int,int> boundaries = make_pair(max(0, newInterval.second - requiredLength + 1), min(n-1, newInterval.first + requiredLength - 1));
                DBG(printf("even boundaries (%d,%d)\n",boundaries.first, boundaries.second));
                int solutionsHere = length(boundaries) - requiredLength + 1;
                numberOfWays += solutionsHere;
                DBG(printf("-> found an even way at values=%d,%d, pos=%d,%d, newInterval=(%d,%d), diff=%d, solutionsHere:%d\n",
                 val, val2, pos, pos2, newInterval.first, newInterval.second, solutionsHere));
            }
        }
        interval.first = min(interval.first, pos);
        interval.second = max(interval.second, pos);
    }
    return make_pair(bestScore, numberOfWays);
}

int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    for (int i=0; i < n; i++)
    {
        scanf("%d", &v[i]);
    }
    pair<LL, LL> p = solveFast(v);
    printf("%lld %lld\n", p.first, p.second);
    return 0;
}