#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <vector> using namespace std; #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define DRI(a) int a; scanf("%d ", &a); #define DRII(a, b) int a, b; scanf("%d %d ", &a, &b); #define DRIII(a, b, c) int a, b, c; scanf("%d %d %d ", &a, &b, &c); #define DRIIII(a, b, c, d) int a, b, c, d; scanf("%d %d %d %d ", &a, &b, &c, &d); #define RI(a) scanf("%d ", &a); #define RII(a, b) scanf("%d %d ", &a, &b); #define RIII(a, b, c) scanf("%d %d %d ", &a, &b, &c); #define RIIII(a, b, c, d) scanf("%d %d %d %d ", &a, &b, &c, &d); #define PB push_back #define MP make_pair #define ff first #define ss second #define vi vector<int> #define pii pair<int,int> #define ll long long #define ull unsigned long long #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; #define MAXLOG 20 int A[500007]; int highIdx[500007]; int low[500007]; int lowLen; int high[500007]; int highLen; int arr[(1<<MAXLOG)]; pii tree[(1<<(MAXLOG+1))]; int lazy[(1<<(MAXLOG+1))]; /** * Build and init tree */ void build_tree(int node, int a, int b) { if(a > b) return; // Out of range if(a == b) { // Leaf node if(a >= highLen) tree[node] = MP(0,500007); else tree[node] = MP(0,highIdx[a]); return; } build_tree(node*2, a, (a+b)/2); // Init left child build_tree(node*2+1, 1+(a+b)/2, b); // Init right child if(tree[node*2].ff >= tree[node*2+1].ff) { tree[node] = tree[node*2]; } else { tree[node] = tree[node*2+1]; } } /** * Increment elements within range [i, j] with value value */ void update_tree(int node, int a, int b, int i, int j, int value) { if(lazy[node] != 0) { // This node needs to be updated tree[node].ff += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a > b || a > j || b < i) // Current segment is not within range [i, j] return; if(a >= i && b <= j) { // Segment is fully within range tree[node].ff += value; if(a != b) { // Not leaf node lazy[node*2] += value; lazy[node*2+1] += value; } return; } update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child if(tree[node*2].ff >= tree[node*2+1].ff) { tree[node] = tree[node*2]; } else { tree[node] = tree[node*2+1]; } } /** * Query tree to get max element value within range [i, j] */ pii query_tree(int node, int a, int b, int i, int j) { if(a > b || a > j || b < i) return MP(-1,-1); // Out of range if(lazy[node] != 0) { // This node needs to be updated tree[node].ff += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a >= i && b <= j) // Current segment is totally within range [i, j] return tree[node]; pii q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child pii q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child pii res; if(q1.ff >= q2.ff) { res = q1; } else { res = q2; } return res; } int Afrom[500007]; int Ato[500007]; int main () { DRI(N); /* FOR(i,0,N) arr[i] = 0; memset(lazy, 0, sizeof lazy); */ FOR(i,0,N) RI(A[i]); if(is_sorted(A,A+N)) { cout << "Cool Array" << endl; return 0; } FOR(i,0,N) { while(lowLen > 0 && low[lowLen-1] > A[i]) lowLen--; if(lowLen == 0 || A[i] > low[lowLen-1]) { low[lowLen++] = A[i]; } } FOR(i,0,N) { if(highLen == 0 || A[i] > high[highLen-1]) { highIdx[highLen] = i; high[highLen++] = A[i]; } } build_tree(1, 0, N-1); /* FOR(i,0,highLen) cout << highIdx[i] << " "; cout << endl; FOR(i,0,lowLen) cout << low[i] << " "; cout << endl; FOR(i,0,highLen) cout << high[i] << " "; cout << endl; */ int lptr = 0; int hptr = 0; low[lowLen++] = 500007; high[highLen++] = 500007; priority_queue<pii> pq; int treeEnd = 0; pair<int,pii> res = MP(-1,MP(500007,500007)); FOR(i,0,N) { if(A[i] != low[lptr] && A[i] != high[hptr]) { // insert to tree int treeFrom = lower_bound(high,high+hptr,A[i])-high; update_tree(1, 0, N-1, treeFrom, treeEnd-1, 1); // insert to pq pq.push(MP(-A[i],i)); Afrom[i] = treeFrom; Ato[i] = treeEnd; } if(A[i] == low[lptr]) { lptr++; // delete based on pq while(!pq.empty()) { pii p = pq.top(); if(-p.ff > A[i]) break; pq.pop(); int idx = p.ss; update_tree(1, 0, N-1, Afrom[idx], Ato[idx]-1, -1); } // query int treeFrom = upper_bound(high,high+hptr,A[i])-high; pii tmp = query_tree(1, 0, N-1, treeFrom, treeEnd-1); //DEB(treeFrom); //DEB(treeEnd); if(tmp.ff != -1) { pair<int,pii> newRes = MP(tmp.ff,MP(tmp.ss,i)); //if(newRes.ss.ff == newRes.ss.ss) continue; //DEB(newRes.ff); //DEB(newRes.ss.ff); //DEB(newRes.ss.ss); if(newRes.ff > res.ff) res = newRes; else if(newRes.ff == res.ff) res = min(res,newRes); //res = min(res,newRes); } } if(A[i] == high[hptr]) { hptr++; // extend tree treeEnd++; } } cout << res.ss.ff+1 << " " << res.ss.ss+1 << endl; return 0; }