#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <cstdio> //#define SHOW using namespace std; const int MAXN = 500000 + 10; const int INFI = 10000000; typedef pair<int,int> PII; // numbers // shift to permuation of 0 ... n-1 int n; vector<int> a; // upper line, stores the id vector<int> u; vector<bool> in_u; // bottom line, stores the id vector<int> b; // to delete, to add // id of element in u -> list of ids vector<vector<int> > to_delete, to_add; void make_to_list( const vector<PII>& list, vector<vector<int> >& to_list ) { to_list.clear(); to_list.resize(n, vector<int>()); int last_id = -1; for( vector<PII>::const_iterator it = list.begin(); it != list.end(); it++ ) { int id = it->second; if ( in_u[id] ) last_id = id; assert( last_id != -1 ); to_list[last_id].push_back(id); } } void prepare(){ // read cin >> n; a = vector<int>(n, 0); for ( int i = 0; i < n; i++ ){ int v; cin >> v; v--; a[i] = v; } // construct upper line u.push_back(0); for ( int i = 1; i < n; i++ ) if ( a[*u.rbegin()] < a[i] ) u.push_back(i); in_u = vector<bool>(n, false); for ( vector<int>::iterator it = u.begin(); it != u.end(); it++ ) in_u[*it] = true; // construct bottom line b.push_back(n-1); for ( int i = n-2; i >= 0; i-- ) if ( a[*b.rbegin()] > a[i] ) b.push_back(i); b = vector<int>(b.rbegin(), b.rend()); // make to_delete vector<PII> list; for ( int i = 0; i < n; i++ ) list.push_back( PII(i,i) ); make_to_list(list, to_delete); // make to_add list.clear(); for ( int i = 0; i < n; i++ ) list.push_back( PII(-a[i],i) ); sort(list.begin(), list.end()); /* printf("to_add's original list\n"); for( int _ = 0; _ < (int) list.size(); _++ ) printf("(%d,%d) ",list[_].first,list[_].second); printf("\n"); */ make_to_list(list, to_add); } void show_prepare(){ printf("a:\n"); for ( int i = 0; i < n; i++ ) printf("%5d", i); printf("\n"); for ( int i = 0; i < n; i++ ) printf("%5d", a[i]); printf("\n"); printf("\n"); printf("u:\n"); for ( int i = 0; i < (int)u.size(); i++ ) printf("%5d", i); printf("\n"); for ( int i = 0; i < (int)u.size(); i++ ) printf("%5d", u[i]); printf("\n"); for ( int i = 0; i < (int)u.size(); i++ ) printf("%5d", a[u[i]]); printf("\n"); printf("\n"); printf("in_u:\n"); for ( int i = 0; i < n; i++ ) printf("%5d", i); printf("\n"); for ( int i = 0; i < n; i++ ) printf("%5s", in_u[i]?"t":"f"); printf("\n"); printf("\n"); printf("b:\n"); for ( int i = 0; i < (int)b.size(); i++ ) printf("%5d", i); printf("\n"); for ( int i = 0; i < (int)b.size(); i++ ) printf("%5d", b[i]); printf("\n"); for ( int i = 0; i < (int)b.size(); i++ ) printf("%5d", a[b[i]]); printf("\n"); printf("\n"); printf("to_delete:\n"); for ( int i = 0; i < n; i++ ){ printf("%5d: ",i); for ( int _ = 0; _ < (int)to_delete[i].size(); _++ ) printf("%5d",to_delete[i][_]); printf("\n"); } printf("\n"); printf("to_add:\n"); for ( int i = 0; i < n; i++ ){ printf("%5d: ",i); for ( int _ = 0; _ < (int)to_add[i].size(); _++ ) printf("%5d",to_add[i][_]); printf("\n"); } printf("\n"); } struct Node { int left, right; bool is_pure; int delta; Node *p_left, *p_right; int largest, index; Node(int left, int right): left(left), right(right), is_pure(true), delta(0) { p_left = p_right = NULL; } void update() { if (is_pure) { largest = delta; index = left; }else{ largest = p_left->largest + delta; index = p_left->index; if ( largest < p_right->largest + delta ){ largest = p_right->largest + delta; index = p_right->index; } } } void modify(int in_delta){ delta += in_delta; update(); } void push_down() { assert(left+1 < right); int mid = (left + right)/2; if (!p_left) p_left = new Node(left, mid); if (!p_right) p_right = new Node(mid, right); p_left->modify(delta); p_right->modify(delta); delta = 0; is_pure = false; } }; struct SegmentTree { Node* root; // segments will have range [0,n) SegmentTree(int n){ root = new Node(0,n); } void modify( Node* node, int left, int right, int delta ){ if ( right <= node->left || left >= node->right ) return; if ( left <= node->left && right >= node->right ){ node->modify(delta); return; } node->push_down(); modify(node->p_left, left, right, delta); modify(node->p_right, left, right, delta); node->update(); } void add( int left, int right, int delta ){ modify(root, left, right, delta); } // result: value, place(left) PII query( Node* node, int left, int right ){ if ( right <= node->left || left >= node->right ) return PII(-INFI, -1); if ( left <= node->left && right >= node->right ) return PII(node->largest, node->index); node->push_down(); PII result_left = query(node->p_left, left, right); PII result_right = query(node->p_right, left, right); PII result = result_left; if (result_right.first > result_left.first) result = result_right; assert(result.first > -INFI); result.first += node->delta; return result; } PII query( int left, int right ){ PII result = query(root, left, right); return result; } }; ///* SegmentTree* tree; void tree_init() { tree = new SegmentTree(b.size()); } // range of index of b that satisfies // if lower-righter than (id,a[id]) // returns left, right, // which means [left, right) PII get_range( int id ){ int l, r; // left = first i that b[i] >= id l = 0, r = b.size(); while ( l < r ) { int mid = (l+r) / 2; if (b[mid] < id) l = mid + 1; else r = mid; } int left = l; // right = first i that a[b[i]] > a[id] l = 0, r = b.size(); while ( l < r ) { int mid = (l+r)/2; if (a[b[mid]] <= a[id]) l = mid + 1; else r = mid; } int right = l; assert(left <= right); #ifdef SHOW printf("get_range(%5d): %5d, %5d\n",id, left, right); #endif return PII(left,right); } void tree_add_point( int id ) { #ifdef SHOW printf("tree_add_point(%5d)\n",id); #endif PII range = get_range(id); int left = range.first, right = range.second; tree->add(left, right, 1); } void tree_delete_point( int id ) { #ifdef SHOW printf("tree_delete_point(%5d)\n",id); #endif PII range = get_range(id); int left = range.first, right = range.second; tree->add(left, right, -1); } PII tree_query( int id ){ #ifdef SHOW printf("tree_query(%5d)\n",id); #endif PII range = get_range(id); int left = range.first, right = range.second; PII result = tree->query(left, right); #ifdef SHOW printf("result: (%5d,%5d)\n", result.first, result.second); #endif return result; } //*/ // naive version /* vector<int> tree; void tree_init(){ tree.clear(); tree.resize(b.size(),0); } void tree_add_point( int id ){ printf("tree_add_point(%5d)\n",id); for (int i = 0; i < (int)b.size(); i++ ) printf("%5d",i); printf("\n"); for (int i = 0; i < (int)b.size(); i++ ){ if ( id <= b[i] && a[b[i]] <= a[id] ){ tree[i] += 1; printf("%5d",1); }else{ printf("%5d",0); } } printf("\n"); for (int i = 0; i < (int)b.size(); i++ ) printf("%5d",tree[i]); printf("\n"); } void tree_delete_point( int id ) { printf("tree_delete_point(%5d)\n",id); for (int i = 0; i < (int)b.size(); i++ ) printf("%5d",i); printf("\n"); for (int i = 0; i < (int)b.size(); i++ ){ if ( id <= b[i] && a[b[i]] <= a[id] ){ tree[i] -= 1; printf("%5d",-1); }else{ printf("%5d",0); } } printf("\n"); for (int i = 0; i < (int)b.size(); i++ ) printf("%5d",tree[i]); printf("\n"); } PII tree_query( int id ){ printf("tree_query(%5d)\n",id); int score = -1, index = -1; for (int i = 0; i < (int)b.size(); i++ ){ if ( id <= b[i] && a[b[i]] <= a[id] ){ if ( tree[i] > score ){ score = tree[i]; index = i; } } } return PII(score, index); } */ int main() { prepare(); #ifdef SHOW show_prepare(); #endif // initialize segment tree tree_init(); // scan all points int best_score = -1; int best_i = -1, best_j = -1; for ( vector<int>::iterator it = u.begin(); it != u.end(); it++ ) { int id = *it; for ( vector<int>::iterator it_add = to_add[id].begin(); it_add != to_add[id].end(); it_add++ ){ tree_add_point( *it_add ); } PII result = tree_query(id); int score = result.first; int j = b[result.second]; if ( score > best_score ) { best_score = score; best_i = id; best_j = j; } for ( vector<int>::iterator it_delete = to_delete[id].begin(); it_delete != to_delete[id].end(); it_delete++ ){ tree_delete_point( *it_delete ); } } assert(best_score > -1); assert(best_i > -1); assert(best_j > -1); best_i += 1; best_j += 1; if (best_score > 1) cout << best_i << " " << best_j << endl; else cout << "Cool Array" << endl; return 0; }