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 $$$\lceil \frac{x}{2} \rceil$$$ 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 $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero) elements. Note that it does not have to be contiguous.
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]$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$ and the number of queries.The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n}$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the range of this query.
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.
""""""

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    indexes = [[] for _ in range(max(a) + 1)]
    prefix_bit_cnts = [0] * (n * 19)
    for (i, x) in enumerate(a):
        indexes[x].append(i)
        for bit in range(19):
            if x & 1 << bit > 0:
                prefix_bit_cnts[bit * n + i] = 1
    for i in range(1, n):
        for bit in range(19):
            prefix_bit_cnts[bit * n + i] += prefix_bit_cnts[bit * n + i - 1]

    def query_bit_cnt(l, r, bit):
        ans = prefix_bit_cnts[bit * n + r]
        if l - 1 >= 0:
            ans -= prefix_bit_cnts[bit * n + l - 1]
        return ans

    def query_x_cnt(l, r, x):
        if x >= len(indexes):
            return 0
        arr = indexes[x]
        arrn = len(arr)
        (lo, hi) = (-1, arrn - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if arr[mid] < l:
                lo = mid
            else:
                hi = mid - 1
        left = lo
        (lo, hi) = (-1, arrn - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if arr[mid] <= r:
                lo = mid
            else:
                hi = mid - 1
        right = lo
        return right - left

    def calc_segments(cnt, gap):
        ans = max(1, gap - 2 * (gap - cnt))
        return ans
    ans = []
    for _ in range(q):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        gap = r - l + 1
        most_common_element = 0
        for bit in range(19):
            if query_bit_cnt(l, r, bit) * 2 >= gap:
                most_common_element |= 1 << bit
        cnt = query_x_cnt(l, r, most_common_element)
        segments = calc_segments(cnt, gap)
        ans.append(segments)
    multiLineArrayPrint(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_right, bisect_left
from random import randrange
mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
d = [[] for _ in range(n + 1)]
for (i, v) in enumerate(a):
    d[v].append(i + 1)
s = [randrange(10 ** 7) for __ in range(23)]
for _ in range(q):
    (l, r) = map(int, input().split())
    tot = r - l + 1
    ans = 0
    ck = set()
    for j in s:
        i = a[j % (r - l + 1) + l - 1]
        if len(d[i]) <= (r - l) // 2 + 1 or i in ck:
            continue
        ck.add(i)
        rig = bisect_right(d[i], r)
        lef = bisect_left(d[i], l)
        if rig - lef > (r - l) // 2 + 1:
            ans = rig - lef
            break
        tot -= rig - lef
        if tot <= (r - l) // 2 + 1:
            break
    if ans:
        print(2 * ans - r + l - 1)
    else:
        print(1)
""""""

def test_generator(n, q, a_max):
    from random import randint
    a = [randint(1, a_max) for _ in range(n)]
    queries = [tuple(sorted([randint(0, n - 1) for _ in range(2)])) for __ in range(q)]
    return (a, queries)

def test_solutions_correctness(n, q, a, queries):
    solutions = solve(n, q, a, queries)
    from collections import Counter
    for i in range(q):
        (l, r) = queries[i]
        max_cnt = 0
        cnt = Counter()
        for j in range(l, r + 1):
            cnt[a[j]] += 1
            max_cnt = max(max_cnt, cnt[a[j]])
        gap = r - l + 1
        for n_seg in range(1, max_cnt + 1):
            if max_cnt - (n_seg - 1) <= ceil((gap - (n_seg - 1)) / 2):
                min_n_seg = n_seg
                break
        if min_n_seg != solutions[i]:
            print(f'a={a} queries={queries} i={i} min_n_seg={min_n_seg} solution={solutions[i]}')
            raise Exception('Wrong answer')
    print(f'Solution Ok.')

def test_solution_time(n, q, a, queries):
    from datetime import datetime
    start = datetime.now()
    solutions = solve(n, q, a, queries)
    end = datetime.now()
    print(f'Time={end - start}')

def run_tests():
    for _ in range(10):
        (n, q) = (10, 10)
        (a, queries) = test_generator(n, q, 2)
        test_solutions_correctness(n, q, a, queries)
        (a, queries) = test_generator(n, q, 10)
        test_solutions_correctness(n, q, a, queries)
        (n, q) = (300000, 300000)
        (a, queries) = test_generator(n, q, 2)
        test_solution_time(n, q, a, queries)
        (a, queries) = test_generator(n, q, 100)
        test_solution_time(n, q, a, queries)
        (a, queries) = test_generator(n, q, 300000)
        test_solution_time(n, q, a, queries)

def solve(n, q, a, queries):
    guess_cnt = 40
    positions = [[] for _ in range(max(a) + 1)]
    query_order = list(range(q))
    query_order.sort(key=lambda i: queries[i][1])
    solutions = [-1] * q
    R = -1
    for i_q in query_order:
        (l, r) = queries[i_q]
        while R + 1 <= r:
            R += 1
            positions[a[R]].append(R)
        gap = r - l + 1
        if gap == 1:
            solutions[i_q] = 1
            continue
        guess_cnt2 = min(guess_cnt, gap)
        delta = (gap - 1) / (guess_cnt2 - 1)
        i = l
        ans = 1
        min_cnt = ceil(gap / 2) + 1
        while i <= r:
            x = a[floor(i)]
            arr = positions[x]
            m = len(arr)
            if min_cnt <= m and arr[m - min_cnt] >= l:
                (lo, hi) = (-1, m - 1)
                while lo < hi:
                    mid = (lo + hi + 1) // 2
                    if arr[mid] < l:
                        lo = mid
                    else:
                        hi = mid - 1
                cnt = m - lo - 1
                ans = gap - 2 * (gap - cnt)
                break
            i += delta
        solutions[i_q] = ans
    return solutions

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    queries = []
    for _ in range(q):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        queries.append((l, r))
    solutions = solve(n, q, a, queries)
    multiLineArrayPrint(solutions)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()