数列 $a_1, a_2, \dots, a_n$ が与えられます。各クエリで、区間 $[l, r]$ 内で最も多く出現する値の出現回数を求めてください。

ただし、今回は正確な答えを求める必要はありません。答えのオーダー（大きさの程度）が分かれば十分です。したがって、正確な答えを $ans$ としたとき、出力する値が $[0.5ans, 2ans]$ の範囲内に収まっていれば正解とみなされます。

入力

1行目に2つの正整数 $n, q$ が与えられ、それぞれ数列の長さとクエリの回数を表します。

続く1行に $n$ 個の正整数が与えられ、それぞれ $a_1, a_2, \dots, a_n$ を表します。

続く $q$ 行の各行に、クエリの区間を表す2つの正整数 $l, r$ が与えられます。

出力

$q$ 行にわたって、各クエリに対する答えを出力してください。

入出力例

入力 1

10 3
1 1 4 5 1 4 1 9 1 9
1 10
1 5
3 10

出力 1

5
3
3

注記

サンプルの出力は正確な答えですが、それぞれ $[3, 10], [2, 6], [2, 6]$ の範囲内の値を出力しても正解となります。

小課題

すべてのデータにおいて、$1 \le n, q \le 10^6$、$1 \le a_i \le n$ を満たします。

テストケース $1 \sim 3$：$n, q \le 10^3$ を満たす。

テストケース $4 \sim 5$：$n \le 10^3$ を満たす。

テストケース $6 \sim 7$：$n, q \le 10^5$ を満たす。

テストケース $8 \sim 10$：特別な制約はない。

注記

本問題は入出力のデータ量が大きいため、高速な入出力が必要になる場合があります。以下のテンプレートを参考にしてください。コメントアウトされている箇所はファイル入出力を行う際に使用します。

using u32 = unsigned;
struct IO_Tp
{
    const static int _I_Buffer_Size = 30 << 20;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static int _O_Buffer_Size = 8 << 20;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    u32 m[10000];

    IO_Tp()
    {
//        freopen("ambiguous.in", "r", stdin);
//        freopen("ambiguous.out", "w", stdout);
        constexpr u32 e0 = '\0\0\0\1', e1 = '\0\0\1\0', e2 = '\0\1\0\0', e3 = '\1\0\0\0';
        int x = 0;
        for (u32 i = 0, c0 = '0000'; i != 10; ++i, c0 += e0)
            for (u32 j = 0, c1 = c0; j != 10; ++j, c1 += e1)
                for (u32 k = 0, c2 = c1; k != 10; ++k, c2 += e2)
                    for (u32 l = 0, c3 = c2; l != 10; ++l, c3 += e3)
                        m[x++] = c3;

        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
    }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res)
    {
        while (!isdigit(*_I_pos))
            ++_I_pos;
        res = *_I_pos++ - '0';
        while (isdigit(*_I_pos))
            res = res * 10 + (*_I_pos++ - '0');
        return *this;
    }

    IO_Tp &operator<<(int x)
    {
        if (x == 0)
        {
            *_O_pos++ = '0';
            return *this; 
        }
        static char _buf[35];
        char *_pos = _buf + 35;
        while (x >= 10000)
            *--reinterpret_cast<u32 *&>(_pos) = m[x % 10000], x /= 10000;
        *--reinterpret_cast<u32 *&>(_pos) = m[x];
        _pos += (x < 1000) + (x < 100) + (x < 10);
        _O_pos = std::copy(_pos, _buf + 35, _O_pos);
        return *this;
    }

    IO_Tp &operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
} IO;