#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct sqrt_dec {
	vector <int> elements;
	int min, max, sum;
};

int n, k;
vector <int> a;
vector <sqrt_dec> arr;

void reading() {
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
}
void building() {
	int len = ceil(sqrt(n));
	arr.resize(len);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i != 0 && i % len == 0)
			cnt++;
		arr[cnt].elements.push_back(a[i]);
	}
	for (int i = 0; i < arr.size(); i++) {
		arr[i].sum = 0;
		arr[i].max = 0;
		arr[i].min = 1000000000;
		for (int j = 0; j < arr[i].elements.size(); j++) {
			arr[i].sum += arr[i].elements[j];
			arr[i].max = max(arr[i].max, arr[i].elements[j]);
			arr[i].min = min(arr[i].min, arr[i].elements[j]);
		}
	}
}

void writing() {
	for (int i = 0; i < arr.size(); i++) {
		cout << "sum = " << arr[i].sum << "; max = " << arr[i].max << "; elements: ";
		for (int j = 0; j < arr[i].elements.size(); j++)
			cout << arr[i].elements[j] << " ";
		cout << endl;
	}
}

int max_query(int l, int r) {
	int request_answer = 0, cur_pos = 0, cnt = 0;
	while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= l) {
		cur_pos += arr[cnt].elements.size();
		cnt++;
	}
	if (cur_pos + arr[cnt].elements.size() <= r) {
		for (int i = l - cur_pos; i < arr[cnt].elements.size(); i++)
			request_answer = max(request_answer, arr[cnt].elements[i]);
		cur_pos += arr[cnt].elements.size();
		cnt++;
		while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= r) {
			request_answer = max(request_answer, arr[cnt].max);
			cur_pos += arr[cnt].elements.size();
			cnt++;
		}
		for (int i = 0; i <= r - cur_pos; i++)
			request_answer = max(request_answer, arr[cnt].elements[i]);
		return request_answer;
	}
	for (int i = l - cur_pos; i <= r - cur_pos; i++) {
		request_answer = max(request_answer, arr[cnt].elements[i]);
	}
	return request_answer;
}

int sum_query(int l, int r) {
	int request_answer = 0, cur_pos = 0, cnt = 0;
	while (cnt <= arr.size() && cur_pos + arr[cnt].elements.size() <= l) {
		cur_pos += arr[cnt].elements.size();
		cnt++;
	}
	if (cur_pos + arr[cnt].elements.size() <= r) {
		for (int i = l - cur_pos; i < arr[cnt].elements.size(); i++)
			request_answer += arr[cnt].elements[i];
		cur_pos += arr[cnt].elements.size();
		cnt++;
		while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= r) {
			request_answer += arr[cnt].sum;
			cur_pos += arr[cnt].elements.size();
			cnt++;
		}
		for (int i = 0; i <= r - cur_pos; i++)
			request_answer += arr[cnt].elements[i];
		return request_answer;
	}
	for (int i = l - cur_pos; i <= r - cur_pos; i++) {
		request_answer += arr[cnt].elements[i];
	}
	return request_answer;
}