import java.io.*;
import java.util.StringTokenizer;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws IOException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  private static class Node {
    private int sum;
    private int maxPrefix;
    private int maxSuffix;
    private int maxS;

    public Node(int val) {
      this.sum = val;
      this.maxPrefix = val;
      this.maxSuffix = val;
      this.maxS = val;
    }
  }

  private static Node[] sgTree;

  public static void buildTree(Node[] sgTree, int root, int left, int right, MyScanner scanner) {
    if (left == right) {
      sgTree[root] = new Node(scanner.nextInt());
      return;
    }

    int mid = (left + right) >>> 1;
    buildTree(sgTree, root << 1, left, mid, scanner);
    buildTree(sgTree, (root << 1) | 1, mid + 1, right, scanner);

    Node leftNode = sgTree[root << 1];
    Node rightNode = sgTree[(root << 1) | 1];

    sgTree[root] = new Node(-1);
    sgTree[root].sum = leftNode.sum + rightNode.sum;
    sgTree[root].maxPrefix = Math.max(leftNode.maxPrefix, leftNode.sum + rightNode.maxPrefix);
    sgTree[root].maxSuffix = Math.max(leftNode.maxSuffix + rightNode.sum, rightNode.maxSuffix);
    sgTree[root].maxS = Math.max(Math.max(leftNode.maxS, rightNode.maxS), leftNode.maxSuffix + rightNode.maxPrefix);
  }

  public static Node query(Node[] sgTree, int root, int left, int right, int x, int y) {
    if (x <= left && right <= y) {
      return sgTree[root];
    }

    int mid = (left + right) >>> 1;
    if (x > mid) {
      return query(sgTree, (root << 1) | 1, mid + 1, right, x, y);
    } else if (mid >= y) {
      return query(sgTree, root << 1, left, mid, x, y);
    } else {
      Node leftNode = query(sgTree, root << 1, left, mid, x, y);
      Node rightNode = query(sgTree, (root << 1) | 1, mid + 1, right, x, y);
      Node sol = new Node(-1);
      sol.sum = leftNode.sum + rightNode.sum;
      sol.maxPrefix = Math.max(leftNode.maxPrefix, leftNode.sum + rightNode.maxPrefix);
      sol.maxSuffix = Math.max(leftNode.maxSuffix + rightNode.sum, rightNode.maxSuffix);
      sol.maxS = Math.max(Math.max(leftNode.maxS, rightNode.maxS), leftNode.maxSuffix + rightNode.maxPrefix);
      return sol;
    }
  }

  public static void main(String[] args) throws IOException {

    try(MyScanner scanner = new MyScanner("sequencequery.in");
        FileWriter fw = new FileWriter("sequencequery.out")) {

      int N = scanner.nextInt();
      int M = scanner.nextInt();

      sgTree = new Node[4*N+1];
      buildTree(sgTree, 1, 1, N, scanner);

      for (int i = 1; i <= M; i++) {
        fw.write(query(sgTree, 1, 1, N, scanner.nextInt(), scanner.nextInt()).maxS + "\n");
      }
    }
  }
}