#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

void beolvas(std::istream &in, std::vector<int> &arfolyam, std::vector<std::pair<int, int>> &kerdesek) {
    size_t n, q;
    in >> n >> q;

    arfolyam.resize(n);
    for (auto i = 0u; i < n; i++) {
        in >> arfolyam[i];
    }

    kerdesek.resize(q);
    for (auto i = 0u; i < q; i++) {
        int v, e;
        in >> v >> e;

        kerdesek[i] = { v, e };
    }
}

void feldolgoz(std::ostream &out, const std::vector<int> &arfolyam, const std::vector<std::pair<int, int>> &kerdesek) {
    static constexpr int max_arfolyam = 500;
    static constexpr bool eladas = false;
    static constexpr bool vetel = true;

    const auto n = arfolyam.size();

    std::vector<std::vector<size_t>> arfolyam_idopontok(max_arfolyam + 1);
    for (auto i = 0u; i < n; i++) {
        arfolyam_idopontok[arfolyam[i]].push_back(i);
    }

    std::vector<std::vector<int>> haszon(max_arfolyam + 1, std::vector<int>(max_arfolyam + 1));
    std::vector<size_t> veteli_idopontok;
    for (auto v_arfolyam = 1; v_arfolyam <= max_arfolyam; v_arfolyam++) {
        std::vector<size_t> uj_veteli_idopotok(veteli_idopontok.size() + arfolyam_idopontok[v_arfolyam].size());
        std::merge(veteli_idopontok.cbegin(), veteli_idopontok.cend(),
                   arfolyam_idopontok[v_arfolyam].cbegin(), arfolyam_idopontok[v_arfolyam].cend(),
                   uj_veteli_idopotok.begin());
        veteli_idopontok = std::move(uj_veteli_idopotok);

        if (veteli_idopontok.empty()) {
            continue;
        }

        std::map<size_t, bool> tranzakciok;
        tranzakciok.emplace(veteli_idopontok[0], vetel);
        int akt_haszon = -arfolyam[veteli_idopontok[0]];

        for (auto e_arfolyam = max_arfolyam; e_arfolyam >= v_arfolyam; e_arfolyam--) {
            for (auto t_elad : arfolyam_idopontok[e_arfolyam]) {
                auto tr = tranzakciok.lower_bound(t_elad);
                
                if (tr != tranzakciok.begin()) {
                    auto elozo_tr = tr;
                    --elozo_tr;

                    if (elozo_tr->second == vetel) {
                        // elozo_tr(v), uj_tr(e), uj_vetel(v), tr(e)

                        auto uj_tr = tranzakciok.emplace(t_elad, eladas).first;
                        akt_haszon += arfolyam[t_elad];

                        auto t_uj_vetel = std::upper_bound(veteli_idopontok.begin(), veteli_idopontok.end(), t_elad);
                        if (t_uj_vetel != veteli_idopontok.end() && (tr == tranzakciok.end() || (*t_uj_vetel < tr->first))) {
                            tranzakciok.emplace(*t_uj_vetel, vetel);
                            akt_haszon -= arfolyam[*t_uj_vetel];

                        } else if (tr != tranzakciok.end()) {
                            akt_haszon -= arfolyam[tr->first];
                            tranzakciok.erase(tr);
                        }
                    }
                }
            }

            haszon[v_arfolyam][e_arfolyam] = akt_haszon;
        }
    }

    for (auto [v_arfolyam, e_arfolyam] : kerdesek) {
        out << haszon[v_arfolyam][e_arfolyam] << '\n';
    }
}

int main() {
    std::vector<int> arfolyam;
    std::vector<std::pair<int, int>> kerdesek;

    beolvas(std::cin, arfolyam, kerdesek);
    feldolgoz(std::cout, arfolyam, kerdesek);

    return 0;
}