Cut and Stick

Baby Ehab has a piece of Cut and Stick with an array $a$ of length $n$ written on it. He plans to grab a pair of scissors and do the following to it:

• pick a range $(l,r)$ and cut out every element $a_l, a_{l+1}, ..., a_r$ in this range;
• stick some of the elements together in the same order they were in the array;
• end up with multiple pieces, where every piece contains some of the elements and every element belongs to some piece.

More formally, he partitions the sequence $a_l, a_{l+1}, ..., a_r$ into subsequences. He thinks a partitioning is beautiful if for every piece (subsequence) it holds that, if it has length $x$, then no value occurs strictly more than $⌈\frac x 2⌉$ times in it.

He didn’t pick a range yet, so he’s wondering: for $q$ ranges $(l,r)$, what is the minimum number of pieces he needs to partition the elements $a_l, a_{l+1}, ..., a_r$ into so that the partitioning is beautiful.

A sequence $b$ is a subsequence of an array $a$ if bb can be obtained from $a$ by deleting some (possibly zero) elements. Note that it does not have to be contiguous.

Input

The first line contains two integers $n$ and $q$ $(1≤n,q≤3⋅10^5)$ — the length of the array aa and the number of queries.

The second line contains $n$ integers $a_1, a_2, ..., a_n (1≤ai≤n)$ — the elements of the array $a$.

Each of the next qq lines contains two integers $l$ and $r$ $(1≤l≤r≤n)$ — the range of this query.

Output

For each query, print the minimum number of subsequences you need to partition this range into so that the partitioning is beautiful. We can prove such partitioning always exists.

Example

input

6 2
1 3 2 3 3 2
1 6
2 5

output

1
2

Note
In the first query, you can just put the whole array in one subsequence, since its length is 6, and no value occurs more than 3 times in it.

In the second query, the elements of the query range are [3,2,3,3]. You can’t put them all in one subsequence, since its length is 4, and 3 occurs more than 2 times. However, you can partition it into two subsequences: [3] and [2,3,3].

思路

用可持久化线段树（主席树）判断区间是否需要分多组，若不需要返回 $-1$，若需要返回众数个数，判断的标准即为众数个数是否大于区间的 $⌈\frac x 2⌉$ 。

若判断出区间要分多组，把众数贡献看作 $1$，非众数贡献看作 $-1$，做前缀和，那么分出的第 $i$ 个区间的结尾是最后一个前缀和为 $i$ 的点，

例如：5 5 1 5 5 1 5 5 2 3， 前缀和为 1 2 1 2 3 2 3 4 3 2，所以第一个区间是 $[1,3]$，第二个区间是 $[4,10]$。

可以明显看出区间的分组个数就是前 $n$ 项前缀和，即 最小分组数 = 众数个数 - 非众数个数​。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5+1;

int a[maxn], rt[maxn], tot;

struct node{
    int val, ls, rs;
}p[maxn<<5];

void push_up(int root) {
    int ls = p[root].ls, rs = p[root].rs;
    p[root].val = p[ls].val + p[rs].val;
}

void update(int &root, int pre, int l, int r, int x) {
    p[root=++tot] = p[pre];
    if (l == r) {
        p[root].val ++;
        return ;
    }
    int mid = (l+r) >> 1;
    if (x <= mid) update(p[root].ls, p[pre].ls, l, mid, x);
    else update(p[root].rs, p[pre].rs, mid+1, r, x);
    push_up(root);
}

int query(int ro, int lo, int l, int r, int k) {
    if (l == r) {
        return p[ro].val - p[lo].val;
    }
    int mid = (l+r) >> 1;
    if (p[p[ro].ls].val - p[p[lo].ls].val > k)
        return query(p[ro].ls, p[lo].ls, l, mid, k);
    else if (p[p[ro].rs].val - p[p[lo].rs].val > k)
        return query(p[ro].rs, p[lo].rs, mid+1, r, k);
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) {
        cin >> a[i];
        update(rt[i], rt[i-1], 1, n, a[i]);
    }
    while(m --) {
        int l, r;
        cin >> l >> r;
        int res = query(rt[r], rt[l-1], 1, n, (r-l+1)/2);
        if (res == -1) cout << 1 << "\n";
        else cout << 2*res - (r-l+1) << "\n";
    }
    return 0;
}