Median Frequency Maximization

In the enchanting APIO country, the young and brilliant student Alice is fascinated by problems that push her mathematical abilities to the limit. One day, while studying a mysterious problem concerning a sequence of length (N), denoted as (A[0], A[1], \ldots, A[N-1]), she encountered an interesting challenge that she just couldn’t resist exploring further.

For any subarray (A[l \ldots r]) (where (0 \le l \le r \le N-1)), we define the function

[ W(l, r, x) = \sum_{i=l}^{r} \mathbb{I}[A[i] = x], ]

which counts the number of times the integer (x) appears in (A[l], \ldots, A[r]).

Furthermore, for any non-empty sequence (B = {B[0], B[1], \ldots, B[k-1]}), its median set (S(B)) is computed as follows:

1. Sort \(B\) in non-decreasing order to obtain \(C[0], C[1], \ldots, C[k-1]\).
2. Define \[ S(B) = \left\{ C\left[\left\lfloor \frac{k-1}{2} \right\rfloor\right], \; C\left[\left\lceil \frac{k-1}{2} \right\rceil\right] \right\}. \]

For example:

• \(S(\{6,3,5,4,6,2,3\}) = \{4\}\).
• \(S(\{4,2,3,1\}) = \{2,3\}\).
• \(S(\{5,4,2,4\}) = \{4\}\).

Alice now wishes to determine the maximum possible value of (\max_{x \in S(A[l\ldots r])} W(l, r, x)) taken over all subarrays ((l, r)). In other words, for every subarray, consider the frequency count of each number in its median set and then choose the maximum count; among all these subarrays, output the highest such frequency.

Your task is to help Alice verify her result by implementing a function that computes this value.

Implementation Details

Implement the following function:

int sequence(int N, std::vector<int> A);

where

• \(N\) is the length of the sequence \(A\).
• \(A\) is an array of \(N\) integers.

The function should return an integer representing the maximum value of (\max_{x \in S(A[l\ldots r])} W(l, r, x)) among all possible subarrays (A[l \ldots r]).

inputFormat

The input consists of two lines:

• The first line contains a single integer \(N\), the length of the sequence.
• The second line contains \(N\) space-separated integers representing the sequence \(A\).

outputFormat

Output a single integer which is the maximum value among all subarrays as described.

sample

3
3 2 3

2