<commit_before><commit_msg>spoj: kgss<commit_after>#include <cstdio>
#include <map>

using namespace std;

typedef pair< int, int > ii;

void init( ii *heap, int *a, int k, int s, int t ) {
  if ( s == t ) {
    heap[ k ] = make_pair( a[ s - 1 ], 0 );
  }
  else {
    init( heap, a, 2 * k, s, ( s + t ) / 2 );
    init( heap, a, 2 * k + 1, ( s + t ) / 2 + 1, t );

    heap[ k ].first = max( heap[ 2 * k ].first, heap[ 2 * k + 1 ].first );
    if ( heap[ k ].first == heap[ 2 * k ].first ) {
      heap[ k ].second = max( heap[ 2 * k ].second, heap[ 2 * k + 1 ].first );
    }
    else {
      heap[ k ].second = max( heap[ 2 * k ].first, heap[ 2 * k + 1 ].second );
    }
  }
}
ii query( ii *heap, int k, int s, int t, int i, int j ) {
  ii l, r, ans;

  if ( s == i && t == j ) {
    return heap[ k ];
  }
  if ( j <= ( s + t ) / 2 ) {
    return query( heap, 2 * k, s, ( s + t ) / 2, i, j );
  }
  if ( i > ( s + t ) / 2 ) {
    return query( heap, 2 * k + 1, ( s + t ) / 2 + 1, t, i, j );
  }

  l = query( heap, 2 * k, s, ( s + t ) / 2, i, ( s + t ) / 2 );
  r = query( heap, 2 * k + 1, ( s + t ) / 2 + 1, t, ( s + t ) / 2 + 1, j );

  ans.first = max( l.first, r.first );
  if ( ans.first == l.first ) {
    ans.second = max( l.second, r.first );
  }
  else {
    ans.second = max( l.first, r.second );
  }
  return ans;
}
void update( ii *heap, int k, int s, int t, int pos, int val ) {
  if ( s == t && s == pos ) {
    heap[ k ] = make_pair( val, 0 );
  }
  else {
    if ( pos <= ( s + t ) / 2 ) {
      update( heap, 2 * k, s, ( s + t ) / 2, pos, val );
    }
    else {
      update( heap, 2 * k + 1, ( s + t ) / 2 + 1, t, pos, val );
    }

    heap[ k ].first = max( heap[ 2 * k ].first, heap[ 2 * k + 1 ].first );
    if ( heap[ k ].first == heap[ 2 * k ].first ) {
      heap[ k ].second = max( heap[ 2 * k ].second, heap[ 2 * k + 1 ].first );
    }
    else {
      heap[ k ].second = max( heap[ 2 * k ].first, heap[ 2 * k + 1 ].second );
    }
  }
}

int main() {
  char op;
  int i, j, n, q, *a;
  ii ans, *heap;

  scanf( "%d", &n );
  a = new int[ n ];
  heap = new ii[ 4 * n ];
  for ( i = 0; i < n; ++i ) {
    scanf( "%d", &a[ i ] );
  }

  init( heap, a, 1, 1, n );
  scanf( "%d\n", &q );
  while ( q-- ) {
    scanf( "%c %d %d\n", &op, &i, &j );
    switch ( op ) {
      case 'Q':
        ans = query( heap, 1, 1, n, i, j );
        printf( "%d\n", ans.first + ans.second );
        break;
      case 'U':
        update( heap, 1, 1, n, i, j );
        break;
    }
  }

  return 0;
}

{'fraction_non_alphanumeric': 0.2184639872662157, 'fraction_numerical': 0.024671707122960605, 'mean_word_length': 1.6242171189979122, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3655613', 'n_tokens_mistral': 1163, 'n_tokens_neox': 1089, 'n_words': 394}