In the enchanting realm of APIO, there lived a young and brilliant student named Alice. Alice had an insatiable curiosity for solving intriguing problems that challenged her mathematical prowess. One day, she stumbled upon a mystical series of numbers with a length of $N$ (that is $A[0],A[1],\dots ,A[N-1]$), and she couldn't resist the allure of exploring its secrets.

Here, she wants to share with you some of her discoveries. But before that, for your convenience, we need to define some things:

• Define $W(l,r,x)$ as $\sum _{i=l}^r\mathbb{I}[A[i]=x]$, i.e., the number of occurrences of x in $A[l]\dots A[r]$.
• For a non-empty integer sequence $B[0],B[1],\dots B[k-1]$, let $S(\{B[0],B[1]\dots B[k-1]\})$ denote its set of medians. Below, Alice will show you how to calculate the set of medians step-by-step:
  • First, sort the elements $B[0],B[1],\dots ,B[k-1]$ in ascending order to obtain the sequence $C[0],C[1],\dots ,C[k-1]$. Then, $S(\{B[0],B[1],\dots ,B[k-1]\})=\{C[\lfloor \frac{k-1}{2}\rfloor ],C[\lceil \frac{k-1}{2}\rceil ]\}$.
  • To enhance your understanding of the calculation of $S$, let's consider a few examples:
    • $S(\{6,3,5,4,6,2,3\})$ = $\{4\}$.
    • $S(\{4,2,3,1\})$ = $\{2,3\}$.
    • $S(\{5,4,2,4\})$ = $\{4\}$.

Alice is eager to find the value of $\underset{x\in S(l,r)}{max}W(l,r,x)$, where $0\le l\le r\le N-1$, as it poses a challenging task. The term $S(l,r)$ represents the set of medians of $A[l]\dots A[r]$ (previously mentioned as $S(\{A[l],\dots ,A[r]\})$). Although Alice has already obtained the answer, she seeks assistance in verifying it and kindly requests your help in programming the calculation.

Implementation Details

You should implement the following procedure:

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

• $N$: the length of sequence $A$.
• $A$: an array of length $N$, describing the sequence $A$.
• This procedure should return an integer representing the maximum value among all possible pairs $(l,r)$.
• This procedure is called exactly once.

Example 1

Consider the following call:

sequence(7, {1, 2, 3, 1, 2, 1, 3});

This procedure should return $3$.

In this case, $S(0,5)=\{1,2\}$, $W(0,5,1)=3$, $W(0,5,2)=2$. So the value of $(0,5)$ is $3$.

It is easy to verify that $(0,5)$ has the greatest value among all possible pairs.

Example 2

Consider the following call:

sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});

This procedure should return $2$.

Example 3

Consider the following call:

sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});

This procedure should return $3$.

Constraints

• $1\le N\le 5\times {10}^5$
• $1\le A[i]\le N$

Subtasks

1. (11 points): $N\le 100$.
2. (17 points): $N\le 2\times {10}^3$.
3. (7 points): There exists an $x$ that satisfies $\mathrm{\forall }0\le i<x$, $A[i]\le A[i+1]$ and $\mathrm{\forall }x<i<N$, $A[i]\le A[i-1]$.
4. (12 points): $A[i]\le 3$.
5. (13 points): $W(0,N-1,A[i])\le 2$ (for each $i$ such that $0\le i\le N-1$).
6. (22 points): $N\le 8\times {10}^4$.
7. (18 points): No additional constraints.

Sample Grader

The sample grader reads input in the following format:

• Line $1$: $N$
• Line $2$: $A[0]$ $A[1]$ $\dots$ $A[N-1]$.

The sample grader prints your output in the following format:

• Line $1$: the return value of sequence.

Attachment Package

The sample grader along with sample test cases are available here: sequence.zip.