#include <bits/stdc++.h> #define clr(x) memset((x), 0, sizeof((x))) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp std::make_pair #define x first #define y second typedef std::pair<int, int> PII; typedef int64_t ll; typedef std::pair<ll, ll> PLL; typedef long double ld; typedef std::pair<ld, ld> PLD; typedef std::pair<double, double> PDD; using namespace std; int nxt() { int a; scanf("%d", &a); return a; } const int N = 1 << 19; int n; int a[N]; PII t[N + N]; int add[N + N]; void build(int v, int tl, int tr) { add[v] = 0; if (tl == tr) { t[v] = mp(0, tl); return; } int tm = (tl + tr) >> 1; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[v] = mp(0, t[v + v + 1].second); } void upd(int v, int tl, int tr, int l, int r, int val) { if (l > r) return; if (l == tl && tr == r) { add[v] += val; return; } int tm = (tl + tr) >> 1; upd(v + v, tl, tm, l, min(tm, r), val); upd(v + v + 1, tm + 1, tr, max(tm + 1, l), r, val); int vall = t[v + v].x + add[v + v]; int valr = t[v + v + 1].x + add[v + v + 1]; if (vall <= valr) { t[v] = mp(valr, t[v + v + 1].second); } else { t[v] = mp(vall, t[v + v].second); } } struct Event { int x, fl; PII seg; Event() {} Event(int x, int fl, const PII &seg) : x(x), fl(fl), seg(seg) { } bool operator < (const Event &r) const { if (x != r.x) return x < r.x; if (fl != r.fl) return fl < r.fl; return seg < r.seg; } }; Event e[N + N]; int sz; void solve() { n = nxt(); for (int i = 0; i < n; ++i) { a[i] = nxt() - 1; } if (is_sorted(a, a + n)) { cout << "Cool Array\n"; return; } vector<int> stl; vector<int> str; for (int i = 0; i < n; ++i) { if (stl.empty()) { stl.pb(i); continue; } if (a[stl.back()] < a[i]) { stl.pb(i); } } for (int i = n - 1; i >= 0; --i) { if (str.empty()) { str.pb(i); continue; } if (a[str.back()] > a[i]) { str.pb(i); } } sz = 0; // for (int i = 0; i < n; ++i) { // cout << a[i] + 1 << " "; // } // cout << endl; // for (int i = 0; i < stl.size(); ++i) { // cout << stl[i] << " "; // } // cout << endl; // for (int i = 0; i < str.size(); ++i) { // cout << str[i] << " "; // } // cout << endl; for (int i = 0; i < n; ++i) { int xl, xr; int yl, yr; xl = lower_bound(stl.begin(), stl.end(), i, [&](int l, int r){ return a[l] < a[r]; }) - stl.begin(); xr = upper_bound(stl.begin(), stl.end(), i) - stl.begin(); yl = lower_bound(str.begin(), str.end(), i, [&](int l, int r){ return a[l] > a[r]; }) - str.begin(); yr = upper_bound(str.begin(), str.end(), i, greater<int>()) - str.begin() - 1; if (xl >= xr) continue; if (yl > yr) continue; e[sz++] = Event(xl, 1, mp(yl, yr)); e[sz++] = Event(xr, 0, mp(yl, yr)); } sort(e, e + sz); int ans = -1; int l = -1, r = -1; int trsize = (int)str.size() - 1; build(1, 0, trsize); for (int i = 0; i < sz; ++i) { assert(e[i].seg.x <= e[i].seg.y); if (e[i].fl) { upd(1, 0, trsize, e[i].seg.x, e[i].seg.y, 1); int curans = t[1].first + add[1]; int curl = stl[e[i].x]; int curr = str[t[1].second]; if (curans > ans) { ans = curans; l = curl; r = curr; } else { if (ans == curans && mp(l, r) > mp(curl, curr)) { l = curl; r = curr; } } } else { upd(1, 0, trsize, e[i].seg.x, e[i].seg.y, -1); } } cout << l + 1 << " " << r + 1 << "\n"; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); double cl0 = clock(); #endif solve(); #ifdef LOCAL cerr << "time: " << (clock() - cl0) / CLOCKS_PER_SEC << endl; #endif }