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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

namespace {
  using std::cin;
  using std::cout;
  using std::is_sorted;
  using std::sort;

  using number_t = size_t;
  using rank_seq_t = std::vector<number_t>;
}

int main() {
  number_t n;
  number_t v;
  number_t answer_max = 0, answer_count = 1;
  rank_seq_t ranks;
  size_t rank_size;
  size_t clamp_size, half_clamp_size;
  rank_seq_t sorted_ranks;

  cin >> n;
  for (size_t k = 0; k < n; ++k) {
    cin >> v;
    ranks.push_back(v);    
  }
  rank_size = ranks.size();
  for (size_t beg = 0; beg < rank_size; ++beg) {
    sorted_ranks.clear();
    for (size_t end = beg; end < rank_size; ++end) {
      clamp_size = end - beg + 1;
      half_clamp_size = clamp_size / 2;      
      auto it_insert = sorted_ranks.begin();
      while (it_insert != sorted_ranks.end() &&
             ranks[end] > *it_insert)
        ++it_insert; 
      sorted_ranks.insert(it_insert, ranks[end]);       
      v = clamp_size + ( (clamp_size % 2 == 1) ? 
                 2 * sorted_ranks[(clamp_size + 1) / 2 - 1] : 
                 sorted_ranks[half_clamp_size - 1] + 
                   sorted_ranks[half_clamp_size] );
      if (v > answer_max) {
        answer_max = v;
        answer_count = 1;
      } else if (v == answer_max) {
        ++answer_count;
      }
    }
  }

  cout << answer_max << ' ' << answer_count;
  return 0;
}