本题是简单版本，因为是离线查询数据量比较小 所以可以用我们的 超级暴力莫队算法

简单的说就是我们用一个 小根堆 和 大根堆 去分别去记录被选择的和未被选择的部分，在动态地移动下去维护题目中“选出恰好一半（向上取整）的队员”的情况

对于 莫队算法 我们只需要在 $Add$ 和 $Sub$ 这两个函数里面修改

• 小根堆 ：$pq2$
• 大根堆 ：$pq1$

就拿样例举例子吧：

• 默认 $L=1,R=0$

• 第一个是 $[1, 4]$ :

$res=1$ 这里 $[1,\ 1]$ 第一个是值，第二个是索引值 下标是代表是否算在最终答案里面

$res=2$

$res=2+3=5$

$res=3+4=7$

• 第二假如是 $[2, 3]$ :

$res=2+3=5$

$res=3$

• 最后是 $[3, 3]$ :

$res=3$

/*
                  暴力出奇迹，  骗分过样例。
                  数学先打表，  ＤＰ看运气。
                  穷举ＴＬＥ，  递推ＵＫＥ。
                  模拟ＭＬＥ，  贪心还ＣＥ。
                  想要骗到分，  就要有方法。
                  图论背模板，  数论背公式。
                  动规背方程，  高精背代码。
                  如果都没背，  干脆输样例。
                模拟只会猜题意, 贪心只能过样例,
                数学上来先打表, DP一般看规律。
                组合数学靠运气, 计算几何瞎暴力,
                图论一顿套模板, 数论只会GCD。

todo               ——----所以——----

                ⣀⣆⣰⣒⣒⡀⢀⠔⠠⠤⡦⠤⠄⢴⠤⠤⠤⢴⠄
                ⢰⣒⣒⣒⣲⠄⠠⡎⠸⠽⠽⠽⠄⠼⡭⠭⠭⡽⠄
                ⢸⠒⠒⢒⣺⠄⠄⡇⡍⣝⣩⢫⠄⣊⣒⣺⣒⣊⡂
                ⢠⠤⠴⠤⠤⠄⢐⢔⠐⠒⡖⠒⠄
                ⣹⢸⢍⢉⢽⠄⢀⢼⠠⠤⡧⠤⠄
                ⡜⡸⠔⠑⠜⡄⠠⡸⢀⣀⣇⣀⠄
                ⢰⣒⣒⣒⣲⠄⠠⡦⢴⠄⡖⢲⠄⡖⢲⠒⢲⠒⡆
                ⢸⣒⣲⣒⣚⠄⠄⡯⢽⠄⣏⣹⠄⡇⡸⠄⢸⣀⡇
                ⣑⣒⣺⣒⣒⡀⢈⠍⠩⣡⠃⣸⠄⣏⣀⣀⣀⣀⡇
                ⡄⠄⡄ ⠐⢲⠒⠄⡆⠢⠄ ⡤⠤⠄⢀⠤⢄
                ⢱⢰⠁ ⠈⢹⣉⠉⡏⡍⠄ ⠗⠒⡄⢸  ⢸
                 ⠇   ⠈⣹⢀⡠⠺⡰⠄ ⠢⠤⠃⠘⠤⠜

*/

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

@SuppressWarnings({"All"})
public class Main
{
    static FastReader sc = new FastReader(System.in);
    static FastWriter pw = new FastWriter(System.out);

    public static void main(String[] ksc)
    {
        new Thread(null, () ->
        {
            int t = 1;
            while (t-- > 0) solve();
            pw.flush();
        }, "codeforces", 1 << 26).start();
    }

    static int n, m, cnt, l, r;
    static long res;
    static mo[] q;
    static long[] ans;
    static int[] a, pos;
    static boolean[] vis;
    static Queue<int[]> pq1, pq2;

    private static void solve()
    {
        n = sc.nextInt();
        m = sc.nextInt();

        a = new int[n + 1];
        pos = new int[n + 1];
        ans = new long[m + 1];
        vis = new boolean[n + 1];
        for (int i = 1; i <= n; i++)
        {
            a[i] = sc.nextInt();
            pos[i] = i / (int) Math.sqrt(n);
        }


        q = new mo[m + 1];
        for (int i = 1; i <= m; i++)
        {
            q[i] = new mo(sc.nextInt(), sc.nextInt(), i);
        }
        Arrays.sort(q, 1, m + 1);

        pq1 = new PriorityQueue<>(Comparator.comparingInt(q -> -q[0]));
        pq2 = new PriorityQueue<>(Comparator.comparingInt(q -> q[0]));

        cnt = 0;
        l = 1;
        r = 0;
        for (int i = 1; i <= m; i++)
        {
            while (q[i].l < l) Add(--l);
            while (q[i].r > r) Add(++r);
            while (q[i].l > l) Sub(l++);
            while (q[i].r < r) Sub(r--);
            ans[q[i].k] = res;
        }

        for (int i = 1; i <= m; i++) pw.println(ans[i]);
    }

    private static void Add(int x)
    {
        pq1.offer(new int[]{a[x], x});
        while (!pq2.isEmpty() && !vis[pq2.peek()[1]]) pq2.poll();
        if (!pq2.isEmpty() && pq1.peek()[0] > pq2.peek()[0])
        {
            int[] ls = pq2.poll();
            pq1.offer(ls);
            vis[ls[1]] = false;
            res -= ls[0];
            cnt--;
        }

        todo();
    }

    private static void Sub(int x)
    {
        if (vis[x])
        {
            vis[x] = false;
            res -= a[x];
            cnt--;
        }

        todo();
    }

    private static void todo()
    {
        int req = (r - l) / 2 + 1;
        while (cnt != req)
        {
            if (cnt < req)
            {
                while (!pq1.isEmpty())
                {
                    int[] elem = pq1.poll();
                    int val = elem[0], idx = elem[1];
                    if (idx < l || idx > r || vis[idx]) continue;
                    res += val;
                    vis[idx] = true;
                    pq2.offer(elem);
                    cnt++;
                    break;
                }
            } else
            {
                while (!pq2.isEmpty())
                {
                    int[] elem = pq2.poll();
                    int val = elem[0], idx = elem[1];
                    if (!vis[idx]) continue;
                    res -= val;
                    vis[idx] = false;
                    pq1.offer(elem);
                    cnt--;
                    break;
                }
            }
        }
    }

    static class mo implements Comparable<mo>
    {
        int l, r, k;

        mo(int l, int r, int k)
        {
            this.l = l;
            this.r = r;
            this.k = k;
        }

        @Override
        public int compareTo(mo o)
        {
            if (pos[this.l] == pos[o.l])
            {
                if (pos[this.l] % 2 == 1) return this.r - o.r;
                return o.r - this.r;
            }
            return pos[this.l] - pos[o.l];
        }
    }

    static class FastReader
    {...}

    static class FastWriter
    {...}
}