#include "oriand.h"

long long oriand(int n, int k, std::vector<long long> a)
{
    long long mask = (1ll << k) - 1;

    std::vector<long long> orST(n * 4);
    std::vector<long long> andST(n * 4);

    auto buildST = [&](auto self, int curr, int cl, int cr) -> void
    {
        if (cl == cr)
        {
            orST[curr] = a[cl];
            andST[curr] = a[cl];
            return;
        }

        int cm = (cl + cr) / 2;
        int left = curr * 2 + 1;
        int right = curr * 2 + 2;

        self(self, left, cl, cm);
        self(self, right, cm + 1, cr);

        orST[curr] = orST[left] | orST[right];
        andST[curr] = andST[left] & andST[right];
    };

    buildST(buildST, 0, 0, n - 1);

    auto queryOr = [&](auto self, int curr, int cl, int cr, int ql, int qr) -> long long
    {
        if (qr < cl || ql > cr) return 0;
        if (cl >= ql && cr <= qr) return orST[curr];

        int cm = (cl + cr) / 2;
        int left = curr * 2 + 1;
        int right = curr * 2 + 2;

        return self(self, left, cl, cm, ql, qr) | self(self, right, cm + 1, cr, ql, qr);
    };

    auto queryAnd = [&](auto self, int curr, int cl, int cr, int ql, int qr) -> long long
    {
        if (qr < cl || ql > cr) return mask;
        if (cl >= ql && cr <= qr) return andST[curr];

        int cm = (cl + cr) / 2;
        int left = curr * 2 + 1;
        int right = curr * 2 + 2;

        return self(self, left, cl, cm, ql, qr) & self(self, right, cm + 1, cr, ql, qr);
    };

    auto getOr = [&](int l, int r) -> long long
    {
        return queryOr(queryOr, 0, 0, n - 1, l, r);
    };

    auto getAnd = [&](int l, int r) -> long long
    {
        return queryAnd(queryAnd, 0, 0, n - 1, l, r);
    };

    long long ans = 0;
    for (int l = 0; l < n; l++)
    {
        int ml = l - 1;
        int mr = n;
        while (mr - ml > 1)
        {
            int mm = (ml + mr) / 2;
            if (getOr(l, mm) == mask) mr = mm;
            else ml = mm;
        }

        int m = mr;
        if (m == n) continue;

        int rl = m;
        int rr = n;
        while (rr - rl > 1)
        {
            int rm = (rl + rr) / 2;
            if (getAnd(m + 1, rm) == 0) rr = rm;
            else rl = rm;
        }

        int r = rr;
        if (r == n) continue;

        ans += n - r;
    }

    return ans;
}
