#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define FWD(i, a, b) for(int i = (a); i < (b); i++) #define BCK(i, a, b) for(int i = (b)-1; i >= (a); i--) #define ALL(s) (s).begin(), (s).end() #define SIZE(x) (int) x.size() #define LOG(x) if(0) cout << #x << " = " << x << endl using PII = pair<int, int>; #define st first #define nd second ostream &operator<<(ostream &out, PII p){ return out << "(" << p.st << ", " << p.nd << ")"; } ostream &operator<<(ostream &out, vector<int> &v){ out << "["; for(auto i : v) out << i << ", "; return out << "]"; } const int N = 5e5; int a[N]; vector<int> upperX, upperY, lowerX, lowerY; struct event { PII range; //lower int time; //upper int extra; event(PII range, int time, int extra):range(range), time(time), extra(extra){} }; bool operator<(event e1, event e2){ return make_pair(e1.time, e1.extra) < make_pair(e2.time, e2.extra); } PII upperRange(PII p){ int begin = lower_bound(ALL(upperY), p.nd) - upperY.begin(); int end = upper_bound(ALL(upperX), p.st) - upperX.begin(); assert(begin < end); return make_pair(begin, end); } PII lowerRange(PII p){ int begin = lower_bound(ALL(lowerY), p.nd, greater<int>()) - lowerY.begin(); int end = upper_bound(ALL(lowerX), p.st, greater<int>()) - lowerX.begin(); assert(begin < end); return make_pair(begin, end); } struct Node { int _maxval; //including extra int _extra; Node *_left; Node *_right; int _begin; int _end; Node(int maxval, int extra, Node *left, Node *right, int begin, int end): _maxval(maxval), _extra(extra), _left(left), _right(right), _begin(begin), _end(end){} Node* addOnRange(int begin, int end, int extra){ if(end <= _begin || _end <= begin) return this; if(begin <= _begin && _end <= end){ _maxval += extra; _extra += extra; return this; } _left = _left->addOnRange(begin, end, extra); _right = _right->addOnRange(begin, end, extra); _maxval = max(_left->_maxval, _right->_maxval) + _extra; return this; } int valueAt(int x){ if(_begin == x && _end == x+1){ return _extra; } if(x < _left->_end) { return _left->valueAt(x) + _extra; } else { return _right->valueAt(x) + _extra; } } int maxIndex(){ if(_end - _begin == 1) return _begin; if(_left->_maxval > _right->_maxval) return _left->maxIndex(); else return _right->maxIndex(); } }; Node* makeNode(int begin, int end){ assert(begin < end); if(end - begin == 1){ return new Node(0, 0, nullptr, nullptr, begin, end); } int mid = (begin + end) / 2; Node* left = makeNode(begin, mid); Node* right = makeNode(mid, end); return new Node(0, 0, left, right, begin, end); } int main(){ int n; assert(scanf("%d", &n) == 1); REP(i, n){ scanf("%d", &a[i]); } if(is_sorted(a, a + n)){ printf("Cool Array\n"); return 0; } int maxA = 0; REP(i, n) { if(a[i] < maxA) continue; maxA = a[i]; upperX.push_back(i+1); upperY.push_back(a[i]); } int minA = -1; BCK(i, 0, n) { if(minA != -1 && a[i] > minA) continue; minA = a[i]; lowerX.push_back(i+1); lowerY.push_back(a[i]); } vector<event> events; REP(i, n){ PII p(i+1, a[i]); PII l = lowerRange(p); PII u = upperRange(p); LOG(p); LOG(u); LOG(l); events.emplace_back(l, u.st, +1); events.emplace_back(l, u.nd, -1); } sort(ALL(events)); Node* node = makeNode(0, SIZE(lowerX)); int bestUpper = -1; int bestLower = -1; int maxInv = 0; for(event e : events) { LOG(e.time); LOG(e.extra); LOG(e.range); node = node->addOnRange(e.range.st, e.range.nd, e.extra); if(node->_maxval > maxInv){ maxInv = node->_maxval; bestUpper = e.time; bestLower = node->maxIndex(); LOG(maxInv); LOG(bestUpper); LOG(bestLower); } } printf("%d %d\n", upperX[bestUpper], lowerX[bestLower]); }