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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <deque>
#include <sys/file.h>
#include <fstream>

using namespace std;

pair<vector<int>, int> build_tree(int n) {
  int number_of_leaves = 1;
  while (number_of_leaves < n) {
    number_of_leaves = number_of_leaves << 1;
  }
  vector<int> tree(number_of_leaves + number_of_leaves - 1 + 1, 0);
  for (int i = 0; i < n; ++i) {
    tree[number_of_leaves + i] = 0;
  }

  return {tree, number_of_leaves};
}

int find_kth_elem(vector<int>& tree, int k, int number_of_leaves, int node) {
  if (node >= number_of_leaves && k == 1) {
    return node;
  }
  if (tree[2 * node] >= k) {
    return find_kth_elem(tree, k, number_of_leaves, 2   * node );
  } else {
    return find_kth_elem(tree, k - tree[2 * node], number_of_leaves, 2   * node + 1);
  }
}

void update_tree(int node, vector<int>& tree, int number_of_leaves) {
  if (node >= number_of_leaves) {
    return;
  }
  update_tree(2 * node + 1, tree, number_of_leaves);
  update_tree(2 * node, tree, number_of_leaves);


  tree[node] += tree[2 * node + 1] + tree[2 * node];
}

void update_node(vector<int>& tree, int node, int number_of_leaves) {
  if (node >= number_of_leaves) {
    return;
  }
  tree[node] = tree[2 * node + 1] + tree[2 * node];
}
// number_of_leaves - indeks pierwszego liscia
void easy_delete(vector<int>& tree, int number, int number_of_leaves) {
  int index = number_of_leaves + number - 1;
  tree[index] = 0;
  while(index > 0) {
    update_node(tree, index, number_of_leaves);
    index /= 2;
  }
}

void easy_add(vector<int>& tree, int number, int number_of_leaves) {
  int index = number_of_leaves + number - 1;
  tree[index] = 1;
  while(index > 0) {
    update_node(tree, index, number_of_leaves);
    index /= 2;
  }
}

int64_t funkcja_celu(int64_t suma_liczby_ocen, pair<int,int> mediana) {
  if (mediana.second == -1) {
    return 0;
  }
  return suma_liczby_ocen + (mediana.second == 2 ? mediana.first : mediana.first * 2);
}

pair<int,int> mediana(vector<int>& drzewo, int ile_jest_jeszcze, int number_of_leaves) {
  if (ile_jest_jeszcze == 0) {
    return {-1,-1};
  }
  if (ile_jest_jeszcze & 1) {
    return {find_kth_elem(drzewo, ile_jest_jeszcze / 2 + 1, number_of_leaves, 1) - number_of_leaves + 1,1};
  } else {
    return {(find_kth_elem(drzewo, ile_jest_jeszcze / 2, number_of_leaves, 1)
        - number_of_leaves + 1 + find_kth_elem(drzewo, ile_jest_jeszcze / 2 + 1, number_of_leaves, 1)
        - number_of_leaves + 1),2};
  }
}


int getMax (vector<int>& drzewo, vector<int>& kolejnosc, int l, int r, int number_of_leaves) {
  auto [licz, mian] = mediana(drzewo, r - l + 1, number_of_leaves);
//  cout <<licz << "/" << mian << " ";
  return (r - l + 1) + (mian == 2 ? licz : 2 * licz);
}



int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> kolejnosc(n, 0);
  int temp;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    kolejnosc[i] = temp;
  }
//  auto[tree, number_of_leaves]  = build_tree(n);
//  update_tree(1,tree, number_of_leaves);
  auto[tree, number_of_leaves]  = build_tree(n);

  int max_val = 2 * n  + 1;
  int max_sposob = 0;
  for (int i = 0; i < n; ++i) {
    easy_add(tree, kolejnosc[i], number_of_leaves);
    for (int j = i + 1; j < n; j++) {
      easy_add(tree, kolejnosc[j], number_of_leaves);
      auto act = getMax(tree, kolejnosc, i, j,number_of_leaves);
//      cout << i << " - " << j << " " << act <<'\n';

      if (act == max_val) {
        max_sposob++;
      }
    }
    for (int j = i + 1; j < n; j++) {
      easy_delete(tree, kolejnosc[j], number_of_leaves);
    }
    easy_delete(tree, kolejnosc[i], number_of_leaves);

  }


//  getMedian(kolejnosc, 1, n - 1);

//cout << getMax(kolejnosc, 0 , 2) << '\n';
//  ofstream myfile;
//  string nazwa = "wyniki" + to_string(max_sposob) + ".out";
//  myfile.open(nazwa.c_str(), std::ios_base::app);
//
//  for (auto c: kolejnosc) {
//    myfile << c << " ";
//  }
//  cout << max_sposob;
//  myfile << '\n';
//  myfile.close();
  cout << max_val << " " << max_sposob + 1;
  return 0;
}