#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cstring> #include <string> #include <set> #include <map> #include <cmath> #include <ctime> #include <sstream> #include <fstream> #include <functional> using namespace std; #ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif typedef long long ll; typedef pair<int, int> pii; #define X first #define Y second #define mp make_pair const int N = (int)1e6 + 10; const int SZ = (int)13e6; int arr[N]; struct Node { int l, r; int sum; Node () : l(0), r(0), sum(0) {} Node (int _s) : l(0), r(0), sum(_s) {} Node (int _l, int _r, int _sum) { l = _l; r = _r; sum = _sum; } }; typedef int Node_ptr; Node tree[SZ]; Node_ptr root[N]; int leftPos[N], rightPos[N]; int cntL, cntR; int mv = 1; int n; Node_ptr newNode(int s) { tree[mv++] = Node(s); return mv - 1; } Node_ptr newNode(Node_ptr l, Node_ptr r) { tree[mv++] = Node(l, r, tree[l].sum + tree[r].sum); return mv - 1; } Node_ptr build(int l, int r) { if (l == r) return newNode(0); int m = (l + r) / 2; return newNode(build(l, m), build(m + 1, r)); } Node_ptr build() { return build(0, n - 1); } Node_ptr addValue(Node_ptr v, int pos, int val, int l, int r) { if (l == r) return newNode(tree[v].sum + val); int m = (l + r) / 2; if (pos <= m) return newNode(addValue(tree[v].l, pos, val, l, m), tree[v].r); return newNode(tree[v].l, addValue(tree[v].r, pos, val, m + 1, r)); } Node_ptr addValue(Node_ptr v, int pos, int val) { return addValue(v, pos, val, 0, n - 1); } int getSum(Node_ptr v, int a, int b, int l, int r) { if (l >= a && r <= b) return tree[v].sum; if (l > b || r < a) return 0; int m = (l + r) / 2; return getSum(tree[v].l, a, b, l, m) + getSum(tree[v].r, a, b, m + 1, r); } int getSum(Node_ptr v, int a, int b) { return getSum(v, a, b, 0, n - 1); } int ifRight[N], ifLeft[N]; int getCountRect(int l, int r, int a, int b) { return getSum(root[r], 0, b) - ifRight[r] - (l == 0 ? 0 : ifLeft[l] - getSum(root[l - 1], 0, a)); } int ansValue = -1; int ansL = -1, ansR = -1; void relaxAnswer(int l, int r, int value) { if (value > ansValue || (value == ansValue && mp(l, r) < mp(ansL, ansR))) { ansValue = value; ansL = l; ansR = r; } } void solve(int l, int r, int a, int b) { while(l <= r && rightPos[b] - leftPos[r] + 1 < ansValue) r--; while(l <= r && arr[leftPos[l]] - arr[rightPos[a]] + 1 < ansValue) l++; if (l > r) return; int mid = (l + r) / 2; int lPos = leftPos[mid]; int c; int bstPos = a - 1; int bstVal = -1; for (c = a; c <= b; c++) { int rPos = rightPos[c]; if (rPos <= lPos || arr[rPos] >= arr[lPos]) continue; int curValue = getCountRect(lPos, rPos, arr[rPos], arr[lPos]); if (curValue > bstVal) { bstVal = curValue; bstPos = c; } } if (bstVal == -1) { c = a; while (c <= b && rightPos[c] <= lPos) c++; solve(l, mid - 1, a, c - 1); solve(mid + 1, r, c, b); return; } relaxAnswer(lPos, rightPos[bstPos], bstVal); solve(l, mid - 1, a, bstPos); solve(mid + 1, r, bstPos, b); } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); arr[i]--; } bool sorted = true; for (int i = 1; i < n; i++) sorted &= (arr[i] > arr[i - 1]); if (sorted) { puts("Cool Array"); return 0; } root[0] = build(); for (int i = 0; i < n; i++) { root[i] = (i == 0 ? root[i] : root[i - 1]); root[i] = addValue(root[i], arr[i], 1); } int prev = -1; for (int i = 0; i < n; i++) { if (prev < arr[i]) { leftPos[cntL++] = i; prev = arr[i]; } } prev = n + 1; for (int i = n - 1; i >= 0; i--) { if (prev > arr[i]) { rightPos[cntR++] = i; prev = arr[i]; } } reverse(rightPos, rightPos + cntR); for (int i = 0; i < n; i++) { ifLeft[i] = (i == 0 ? 0 : getSum(root[i - 1], 0, arr[i])); ifRight[i] = getSum(root[i], 0, arr[i] - 1); } for (int i = 0; i < cntL; i++) eprintf("%d ", leftPos[i] ); eprintf("\n"); for (int i = 0; i < cntR; i++) eprintf("%d ", rightPos[i] ); eprintf("\n"); solve(0, cntL - 1, 0, cntR - 1); printf("%d %d\n", ansL + 1, ansR + 1); return 0; }