#include<iostream>
#include<algorithm>
#include<cstring> //For memset
#include<climits>
#include<cmath>
#define MAX 402
#define inf LONG_MAX
using namespace std ;
long long arr[MAX];
//function definition
//void update(long long node, long long a, long long b, long long i, long long j , long long value);
long long query(long long node , long long a , long long b , long long i , long long j, long long []);
void build_tree(long long node, long long a, long long b, long long []);
//function to find the middle value
inline long long getMid (long long a , long long b){
return (a+b)/2;
}
//Find the maximum of three numbers
inline long long max(long long a , long long b , long long c){
if (a > b){
if(a > c)
return a ;
else
return c ;
}
else{
if(b > c)
return b ;
else
return c ;
}
}
//Build segment tree
void build_tree(long long node , long long a , long long b, long long tree[]){
if (a > b){
return ; // out of range
}
if(a == b){
tree[node] = arr[a];
return ;
}
long long mid = getMid(a , b);
build_tree(node*2 , a , mid, tree);
build_tree(node*2+1 , mid+1 , b, tree);
tree[node] = (tree[node*2] + tree[node*2 + 1]);
}
long long queryUtil(long long node , long long i , long long j, long long tree [] ){
if(i == j){ //Leaf node
return tree[node];
}
else{ //Other nodes
long long mid = getMid( i , j);
long long result = max(queryUtil(node*2 , i , mid, tree) , queryUtil(node*2 + 1 ,mid+1 ,j, tree) , tree[node]);
return result ;
}
}
//Query tree
long long query(long long node , long long a , long long b , long long i , long long j, long long tree []){
if(a > b || a > j || b < i)
return -inf; // Out of range
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return queryUtil(node , i , j, tree);
long long mid = getMid(a , b);
long long q1 = query(node*2, a, mid, i, j, tree); // Query left child
long long q2 = query(1+node*2, mid + 1, b, i, j, tree); // Query right child
long long res = max(q1 , q2);// Return final result
return res;
}
//Driver Program
int main()
{
long long n ,i , l , r , m ;
long long *tree;
long long h ;
//cout << "Enter the number of elements in the array\t";
cin >> n ;
//Input
for(i = 1 ;i<=n;i++){
cin >> arr[i];
}
h = ceil(log2(n));
tree = new long long [ (long long) ( pow (2, h+ 1) ) ];
//initializing the array
memset(tree , 0, sizeof(tree));
//Build Tree
build_tree(1 , 1, n, tree);
cin >> m ;
while(m--){
cin >> l >> r ;
cout << query(1 , 1 , n , l , r, tree) << endl;
}
return 0 ;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8Y3N0cmluZz4gLy9Gb3IgbWVtc2V0CiNpbmNsdWRlPGNsaW1pdHM+CiNpbmNsdWRlPGNtYXRoPgoKI2RlZmluZSBNQVggNDAyIAojZGVmaW5lIGluZiBMT05HX01BWAp1c2luZyBuYW1lc3BhY2Ugc3RkIDsKCmxvbmcgbG9uZyBhcnJbTUFYXTsKCi8vZnVuY3Rpb24gZGVmaW5pdGlvbgovL3ZvaWQgdXBkYXRlKGxvbmcgbG9uZyBub2RlLCBsb25nIGxvbmcgYSwgbG9uZyBsb25nIGIsIGxvbmcgbG9uZyBpLCBsb25nIGxvbmcgaiAsIGxvbmcgbG9uZyB2YWx1ZSk7CmxvbmcgbG9uZyBxdWVyeShsb25nIGxvbmcgbm9kZSAsIGxvbmcgbG9uZyBhICwgbG9uZyBsb25nIGIgLCBsb25nIGxvbmcgaSAsIGxvbmcgbG9uZyBqLCBsb25nIGxvbmcgW10pOwoKdm9pZCBidWlsZF90cmVlKGxvbmcgbG9uZyBub2RlLCBsb25nIGxvbmcgYSwgbG9uZyBsb25nIGIsIGxvbmcgbG9uZyBbXSk7CgovL2Z1bmN0aW9uIHRvIGZpbmQgdGhlIG1pZGRsZSB2YWx1ZQppbmxpbmUgbG9uZyBsb25nIGdldE1pZCAobG9uZyBsb25nIGEgLCBsb25nIGxvbmcgYil7CiAgICByZXR1cm4gKGErYikvMjsKfQoKLy9GaW5kIHRoZSBtYXhpbXVtIG9mIHRocmVlIG51bWJlcnMKaW5saW5lIGxvbmcgbG9uZyBtYXgobG9uZyBsb25nIGEgLCBsb25nIGxvbmcgYiAsIGxvbmcgbG9uZyBjKXsKICAgIGlmIChhID4gYil7CiAgICAgICAgaWYoYSA+IGMpCiAgICAgICAgICAgIHJldHVybiBhIDsKICAgICAgICBlbHNlIAogICAgICAgICAgICByZXR1cm4gYyA7CiAgICB9CiAgICBlbHNlewogICAgICAgIGlmKGIgPiBjKQogICAgICAgICAgICByZXR1cm4gYiA7CiAgICAgICAgZWxzZSAKICAgICAgICAgICAgcmV0dXJuIGMgOwogICAgfQp9CgovL0J1aWxkIHNlZ21lbnQgdHJlZQp2b2lkIGJ1aWxkX3RyZWUobG9uZyBsb25nIG5vZGUgLCBsb25nIGxvbmcgYSAsIGxvbmcgbG9uZyBiLCBsb25nIGxvbmcgdHJlZVtdKXsKICAgIGlmIChhID4gYil7CiAgICAgICAgcmV0dXJuIDsgLy8gb3V0IG9mIHJhbmdlCiAgICB9CiAgICBpZihhID09IGIpewogICAgICAgIHRyZWVbbm9kZV0gPSBhcnJbYV07CiAgICAgICAgcmV0dXJuIDsKICAgIH0KICAgIGxvbmcgbG9uZyBtaWQgPSBnZXRNaWQoYSAsIGIpOwogICAgYnVpbGRfdHJlZShub2RlKjIgLCBhICwgbWlkLCB0cmVlKTsKICAgIGJ1aWxkX3RyZWUobm9kZSoyKzEgLCBtaWQrMSAsIGIsIHRyZWUpOwogICAgdHJlZVtub2RlXSA9ICh0cmVlW25vZGUqMl0gKyB0cmVlW25vZGUqMiArIDFdKTsKfQoKbG9uZyBsb25nIHF1ZXJ5VXRpbChsb25nIGxvbmcgbm9kZSAsIGxvbmcgbG9uZyBpICwgbG9uZyBsb25nIGosIGxvbmcgbG9uZyB0cmVlIFtdICl7CiAgICBpZihpID09IGopeyAvL0xlYWYgbm9kZQogICAgICAgIHJldHVybiB0cmVlW25vZGVdOwogICAgfQogICAgZWxzZXsgLy9PdGhlciBub2RlcwogICAgICAgIGxvbmcgbG9uZyBtaWQgPSBnZXRNaWQoIGkgLCBqKTsKICAgICAgICBsb25nIGxvbmcgcmVzdWx0ID0gbWF4KHF1ZXJ5VXRpbChub2RlKjIgLCBpICwgbWlkLCB0cmVlKSAsIHF1ZXJ5VXRpbChub2RlKjIgKyAxICxtaWQrMSAsaiwgdHJlZSkgLCB0cmVlW25vZGVdKTsKICAgICAgICByZXR1cm4gcmVzdWx0IDsgCiAgICB9Cn0KCi8vUXVlcnkgdHJlZQpsb25nIGxvbmcgcXVlcnkobG9uZyBsb25nIG5vZGUgLCBsb25nIGxvbmcgYSAsIGxvbmcgbG9uZyBiICwgbG9uZyBsb25nIGkgLCBsb25nIGxvbmcgaiwgbG9uZyBsb25nIHRyZWUgW10pewogICAgaWYoYSA+IGIgfHwgYSA+IGogfHwgYiA8IGkpCiAgICAgICAgcmV0dXJuIC1pbmY7IC8vIE91dCBvZiByYW5nZQoKICAgIGlmKGEgPj0gaSAmJiBiIDw9IGopIC8vIEN1cnJlbnQgc2VnbWVudCBpcyB0b3RhbGx5IHdpdGhpbiByYW5nZSBbaSwgal0KICAgICAgICByZXR1cm4gcXVlcnlVdGlsKG5vZGUgLCBpICwgaiwgdHJlZSk7IAoKICAgIGxvbmcgbG9uZyBtaWQgPSBnZXRNaWQoYSAsIGIpOwogICAgbG9uZyBsb25nIHExID0gcXVlcnkobm9kZSoyLCBhLCBtaWQsIGksIGosIHRyZWUpOyAvLyBRdWVyeSBsZWZ0IGNoaWxkCiAgICBsb25nIGxvbmcgcTIgPSBxdWVyeSgxK25vZGUqMiwgbWlkICsgMSwgYiwgaSwgaiwgdHJlZSk7IC8vIFF1ZXJ5IHJpZ2h0IGNoaWxkCgogICAgbG9uZyBsb25nIHJlcyA9IG1heChxMSAsIHEyKTsvLyBSZXR1cm4gZmluYWwgcmVzdWx0CiAgICAKICAgIHJldHVybiByZXM7Cn0KCi8vRHJpdmVyIFByb2dyYW0KaW50IG1haW4oKQp7CiAgICBsb25nIGxvbmcgbiAsaSAsIGwgLCByICwgbSA7IAogICAgbG9uZyBsb25nICp0cmVlOwogICAgbG9uZyBsb25nIGggIDsKICAgIC8vY291dCA8PCAiRW50ZXIgdGhlIG51bWJlciBvZiBlbGVtZW50cyBpbiB0aGUgYXJyYXlcdCI7CiAgICBjaW4gPj4gbiA7CgogICAgLy9JbnB1dAogICAgZm9yKGkgPSAxIDtpPD1uO2krKyl7CiAgICAgICAgY2luID4+IGFycltpXTsKICAgIH0KICAgIGggPSBjZWlsKGxvZzIobikpOwogICAgdHJlZSA9IG5ldyBsb25nIGxvbmcgWyAobG9uZyBsb25nKSAoIHBvdyAoMiwgIGgrIDEpICkgXTsKICAgIC8vaW5pdGlhbGl6aW5nIHRoZSBhcnJheQogICAgbWVtc2V0KHRyZWUgLCAwLCBzaXplb2YodHJlZSkpOwogICAgLy9CdWlsZCBUcmVlCiAgICBidWlsZF90cmVlKDEgLCAxLCBuLCB0cmVlKTsKICAgIGNpbiA+PiBtIDsKICAgIHdoaWxlKG0tLSl7CiAgICAgICAgY2luID4+IGwgPj4gciA7CiAgICAgICAgY291dCA8PCBxdWVyeSgxICwgMSAsIG4gLCBsICwgciwgdHJlZSkgPDwgZW5kbDsKICAgIH0KcmV0dXJuIDAgOwp9