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 <algorithm>
#include <cstdint>
#include <cstdio>
#include <vector>

struct Data {
  int min;
  int max;
  int score;

  bool operator<(const Data& data) const { return max < data.max; }
};

using Numbers = std::vector<int>;

void buildPrefix(const Numbers& numbers, std::vector<Data>& out) {
  std::vector<int> buffer;
  for (int i = 0; i < numbers.size(); ++i) {
    if (buffer.empty() || buffer.back() < numbers[i]) {
      buffer.push_back(numbers[i]);
    }
    out[i + 1] = {buffer.front(), buffer.back(), static_cast<int>(buffer.size())};
  }
}

void buildSuffix(const Numbers& numbers, std::vector<Data>& out) {
  std::vector<int> buffer;
  for (int i = numbers.size() - 1; 0 <= i; --i) {
    while (!buffer.empty() && buffer.back() < numbers[i]) {
      buffer.pop_back();
    }
    if (buffer.empty() || numbers[i] < buffer.back()) {
      buffer.push_back(numbers[i]);
    }
    out[i + 1] = {buffer.back(), buffer.front(), static_cast<int>(buffer.size())};
  }
}

std::vector<Data>::const_iterator findElement2(const std::vector<Data>::const_iterator begin, const std::vector<Data>::const_iterator end, const int value) {
  for (auto it = begin; it < end; it++) {
    if (value < it->max) {
      return it;
    }
  }
  return end;
}

std::vector<Data>::const_iterator findElement(const std::vector<Data>::const_iterator begin, const std::vector<Data>::const_iterator end, const int value) {
  const Data element({0, value, 0});
  auto it = std::lower_bound(begin, end, element);
  if (it != end && it->max == element.max) {
    it++;
  }
  return it;
}

int getScore(const std::vector<Data>& prefix, const std::vector<Data>& suffix, const int n, const int suffixSize) {
  int score = suffix[suffixSize].score;
  const auto end = prefix.cbegin() + suffixSize;
  const auto it = findElement(prefix.cbegin() + 1, end, suffix[suffixSize].max);
  if (it != end) {
    const auto score2 = prefix[suffixSize].score - (it - 1)->score;
    const auto i = static_cast<int>(std::distance(prefix.begin(), it));
    score += score2;
  }
  return score;
}

int getScore2(const std::vector<Data>& prefix, const std::vector<Data>& suffix, const int n, const int suffixSize) {
  int score = suffix[suffixSize].score;
  for (int i = 1; i < suffixSize; ++i) {
    if (suffix[suffixSize].max < prefix[i].max) {
      const auto score2 = prefix[suffixSize].score - prefix[i - 1].score;
      score += score2;
      break;
    }
  }
  return score;
}

int main() {
  int n;
  scanf("%d", &n);
  Numbers numbers(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &numbers[i]);
  }
  std::vector<Data> prefix(n + 1), suffix(n + 1);
  buildPrefix(numbers, prefix);
  buildSuffix(numbers, suffix);

  if (n == 1) {
    printf("1\n");
    return 0;
  }

  int score = prefix[1].score;
  for (int i = 1; i <= n; ++i) {
    score = std::max(score, getScore(prefix, suffix, n, i));
  }
  printf("%d\n", score);
  return 0;
}