小红有一个数组，这个数组中有 个数 。 小红有 次询问，每次询问给定一个区间 ，询问区间连续子段和的绝对值最大是多少，即区间存在 使得 ，求最大的 是多少。

输入描述:

第一行输入一个整数 表示数组的长度。第二行输入 个整数 表示数组的元素。第三行输入一个整数 表示询问的次数。接下来 行，每行输入两个整数 表示询问的区间。

输出描述:

输出 行，每行输出一个整数表示对应询问的答案。