#include <bits/stdc++.h>
using namespace std;
#define long long int
const int MAXN = 2e5 + 5;
int a[MAXN];
int A0[MAXN];
int A1[MAXN];
int AD_[MAXN];
 
void solve() {
    int n, q;
    if (!(cin >> n >> q)) return;
 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
 
    A0[0] = 0;
    A1[0] = 0;
    AD_[0] = 0;
 
    for (int i = 0; i < n; ++i) {
        A0[i + 1] = A0[i] + (a[i] == 0);
        A1[i + 1] = A1[i] + (a[i] == 1);
    }
 
    for (int i = 0; i < n - 1; ++i) {
        AD_[i + 1] = AD_[i] + (a[i] == a[i + 1]);
    }
 
    for (int k = 0; k < q; ++k) {
        int l, r;
        if (!(cin >> l >> r)) return;
 
        int count0 = A0[r] - A0[l - 1];
        int count1 = A1[r] - A1[l - 1];
 
        int total_cost = -1;
 
        if (count0 % 3 == 0 && count1 % 3 == 0) {
            int total_ops = (int)(count0 / 3) + (int)(count1 / 3);
 
            total_cost = total_ops;
 
            if (count0 == count1) {
 
                int adjacent_equal_count = AD_[r - 1] - AD_[l - 1];
 
                if (adjacent_equal_count == 0) {
                    total_cost += 1;
                }
            }
        }
 
        cout << total_cost << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    while (t--) {
        solve();
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbG9uZyBsb25nIGludApjb25zdCBpbnQgTUFYTiA9IDJlNSArIDU7CmludCBhW01BWE5dOwppbnQgQTBbTUFYTl07CmludCBBMVtNQVhOXTsKaW50IEFEX1tNQVhOXTsKCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgbiwgcTsKICAgIGlmICghKGNpbiA+PiBuID4+IHEpKSByZXR1cm47CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBjaW4gPj4gYVtpXTsKICAgIH0KCiAgICBBMFswXSA9IDA7CiAgICBBMVswXSA9IDA7CiAgICBBRF9bMF0gPSAwOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgQTBbaSArIDFdID0gQTBbaV0gKyAoYVtpXSA9PSAwKTsKICAgICAgICBBMVtpICsgMV0gPSBBMVtpXSArIChhW2ldID09IDEpOwogICAgfQogICAgCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG4gLSAxOyArK2kpIHsKICAgICAgICBBRF9baSArIDFdID0gQURfW2ldICsgKGFbaV0gPT0gYVtpICsgMV0pOwogICAgfQoKICAgIGZvciAoaW50IGsgPSAwOyBrIDwgcTsgKytrKSB7CiAgICAgICAgaW50IGwsIHI7CiAgICAgICAgaWYgKCEoY2luID4+IGwgPj4gcikpIHJldHVybjsKCiAgICAgICAgaW50IGNvdW50MCA9IEEwW3JdIC0gQTBbbCAtIDFdOwogICAgICAgIGludCBjb3VudDEgPSBBMVtyXSAtIEExW2wgLSAxXTsKICAgICAgICAKICAgICAgICBpbnQgdG90YWxfY29zdCA9IC0xOwoKICAgICAgICBpZiAoY291bnQwICUgMyA9PSAwICYmIGNvdW50MSAlIDMgPT0gMCkgewogICAgICAgICAgICBpbnQgdG90YWxfb3BzID0gKGludCkoY291bnQwIC8gMykgKyAoaW50KShjb3VudDEgLyAzKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIHRvdGFsX2Nvc3QgPSB0b3RhbF9vcHM7CgogICAgICAgICAgICBpZiAoY291bnQwID09IGNvdW50MSkgewogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBpbnQgYWRqYWNlbnRfZXF1YWxfY291bnQgPSBBRF9bciAtIDFdIC0gQURfW2wgLSAxXTsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYgKGFkamFjZW50X2VxdWFsX2NvdW50ID09IDApIHsKICAgICAgICAgICAgICAgICAgICB0b3RhbF9jb3N0ICs9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgdG90YWxfY29zdCA8PCAiXG4iOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKCiAgICBpbnQgdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQoKICAgIHJldHVybiAwOwp9

MgoxMiA0CjAgMCAxIDEgMCAxIDAgMSAwIDEgMSAwCjEgMTIKMiA3CjUgMTAKNiAxMQo2IDMKMCAwIDAgMSAxIDEKMSAzCjQgNgoxIDYK

2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6