from itertools import combinations
def solve(a, queries):
    n=len(a)
    dp=[]
    for i in range(n):
        dp+=[[0]*n]     
    #print(dp)
    
    for i in range(n):
        for j in range(n):
            if i==j:
                dp[i][j]=a[j]
            elif j>i:
                dp[i][j]=max(a[i:j+1])    
    #print(dp)
    
    l=[]
    for x,y in queries:
        count=0
        if x==y:
            print(dp[x-1][y-1])
        else:
            for i in range(x-1,y):
                for j in range(i,y):
                    #print(i,j)
                    count+=dp[i][j]
            print(count)
        
    #print(l)
    #return l  

public static List<Integer> solve(List<Integer> a, List<List<Integer>> queries) {
        int n = a.size();
        int[][] arr = new int[n][n];
        List<Integer> ans = new ArrayList<>();
        for (int i=0; i< n ; i++) {
             arr[i][i] = a.get(i);            
            for (int j=i+1; j<n; j++) {
                if (a.get(j) > arr[i][j-1]) {
                    arr[i][j] = a.get(j);
                }
                else arr[i][j] = arr[i][j-1];
            }
        }
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        int[][] sum = new int[n][n];
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                if (j==0) {
                    sum[i][0] = arr[i][0];
                }
                else {
                    sum[i][j] = sum[i][j-1] + arr[i][j];
                }
                System.out.print(sum[i][j]+" ");
            }
            System.out.println();
        }
        for (int i=0; i<queries.size(); i++) {
            int l = queries.get(i).get(0)-1;
            int r = queries.get(i).get(1)-1;
            int maxSum = 0;
            for (int j=l;j<=r;j++){
                if (l==0){
                    maxSum += sum[j][r];
                }
                else {
                    maxSum += sum[j][r] - sum[j][l-1];
                }
            }
            ans.add(maxSum);
        }
        return ans;

    }

def solve(a, queries):
    res = []
    for q in queries:
        sum = 0
        for i in range(q[0]-1,q[1]):
            sum += a[i]
            for j in range(i+1,q[1]):
                sum += max(a[i:j+1])
        res.append(sum)
    return res