#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//	Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {					
	int answer;
	answer = 1 << (int)(log2((double)number - 1) + 1);
	return answer;
}

//	The structure describing the components from which consists a tree
struct Node {
	int answer; 		
	int sumOnPrefix;
	int sumOnSuffix;
	int sumOnSegment;
	//	Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
	Node() {
		answer = INF;
		sumOnPrefix = INF;
		sumOnSuffix = INF;
		sumOnSegment = INF;
	}
	// Constructs a node by a value of the initial sequence of numbers
	Node(int value) {
		answer = value;
		sumOnPrefix = value;
		sumOnSuffix = value;
		sumOnSegment = value;
	}
};

//	Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
	Node crossedNode;
	crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
	crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
	crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
	crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
	return crossedNode;
}

//	Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
	if (left == right) {
		tree[currentNode] = Node(base[left]);
	} else {
		int leftChild = 2 * currentNode;
		int middle = (left + right) / 2;
		build(base, tree, leftChild, left, middle);
		build(base, tree, leftChild + 1, middle + 1, right);
		// Use the previously described function to get the value of parent by his children
		tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
	}
}

// Funtion, that updates value in specified postion
void update(Node *tree, int currentNode, int left, int right, int position, int newValue) { 
	if (left == right) {
		tree[currentNode] = Node(newValue);
	} else {
		int leftChild = 2 * currentNode;
		int middle = (left + right) / 2;
		if (position <= middle) {
			update(tree, leftChild, left, middle, position, newValue);
		} else {
			update(tree, leftChild + 1, middle + 1, right, position, newValue);
		}
		tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
	}
}

//	Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
	if (left == leftBorder && right == rightBorder) {
		return tree[currentNode];
	}
	int leftChild = 2 * currentNode;
	int middle = (left + right) / 2;
	if (rightBorder <= middle) {
		return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
	}
	if (leftBorder > middle) {
		return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
	}
	return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
		answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
	std::ios::sync_with_stdio(false);
	unsigned int quantityOfNumbers;
	cin >> quantityOfNumbers;
	int *base = new int[quantityOfNumbers];		//	A given sequence of numbers	
	for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
		cin >> base[indexOfNumber];
	}
	int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
	Node *tree = new Node[sizeOfTree];
	build(base, tree, 1, 0, quantityOfNumbers - 1);
	unsigned int quantityOfRequests;
	cin >> quantityOfRequests;
	for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
		unsigned int request, leftBorder, rightBorder;
		cin >> request >> leftBorder >> rightBorder;
		if (request == 0) {
			update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder);
		} else if (request == 1) {
			cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
		}
	}
	return 0;
}