#include <algorithm> #include <cstdio> #include <cstring> #include <climits> #include <utility> #include <vector> const int N = 500000; int a[N], x_0[N], x_1[N], y_0[N], y_1[N], add[N << 1]; std::pair<int, int> max[N << 1]; std::vector<std::pair<int, int>> ls, rs; int get_id(int l, int r) { return l + r | l != r; } void build(int l, int r) { int id = get_id(l, r); max[id] = {0, r}; if (l < r) { int m = l + r >> 1; build(l, m); build(m + 1, r); } } void cover(int l, int r, int a, int b, int c) { if (b < l || r < a) { return; } int id = get_id(l, r); if (a <= l && r <= b) { add[id] += c; max[id].first += c; return; } int m = l + r >> 1; cover(l, m, a, b, c); cover(m + 1, r, a, b, c); max[id] = std::max(max[get_id(l, m)], max[get_id(m + 1, r)]); max[id].first += add[id]; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++ i) { scanf("%d", a + i); } memset(x_0, -1, sizeof(x_0)); for (int i = 0; i < n; ++ i) { if (ls.empty() || ls.back().first < a[i]) { ls.push_back({a[i], i}); } else { x_0[i] = std::lower_bound(ls.begin(), ls.end(), std::make_pair(a[i], 0)) - ls.begin(); x_1[i] = ls.size(); } } memset(y_0, -1, sizeof(y_0)); for (int i = n - 1; i >= 0; -- i) { if (rs.empty() || rs.back().first < -a[i]) { rs.push_back({-a[i], i}); } else { y_0[i] = std::lower_bound(rs.begin(), rs.end(), std::make_pair(-a[i], 0)) - rs.begin(); y_1[i] = rs.size(); } } std::vector<std::pair<int, int>> events; for (int i = 0; i < n; ++ i) { if (~x_0[i] && ~y_0[i]) { // printf("%d [%d, %d) x [%d, %d)\n", a[i], x_0[i], x_1[i], y_0[i], y_1[i]); events.push_back({x_0[i], n + i}); events.push_back({x_1[i], i}); } } std::sort(events.begin(), events.end()); int m = rs.size(); memset(add, 0, sizeof(*add) * (m << 1)); build(0, m - 1); std::pair<int, std::pair<int, int>> best{0, {INT_MAX, INT_MAX}}; for (const auto &e : events) { int i = e.second; if (i >= n) { i -= n; cover(0, m - 1, y_0[i], y_1[i] - 1, 1); int root = get_id(0, m - 1); best = std::max(best, {max[root].first, {-e.first, max[root].second}}); } else { cover(0, m - 1, y_0[i], y_1[i] - 1, -1); } } if (best.first) { int x = -best.second.first; int y = best.second.second; printf("%d %d\n", ls[x].second + 1, rs[y].second + 1); } else { std::vector<int> q; std::pair<int, int> best(INT_MAX, INT_MAX); for (int i = n - 1; i >= 0; -- i) { while (!q.empty() && a[i] < a[q.back()]) { q.pop_back(); } if (!q.empty()) { best = std::min(best, std::make_pair(i, q.back())); } q.push_back(i); } if (best.first < INT_MAX) { printf("%d %d\n", best.first + 1, best.second + 1); } else { puts("Cool Array"); } } return 0; }