Background

Due to some bugs, submitting with C++14 (GCC9) will cause a compilation error. Please submit using C++14 and other languages.

When submitting, you do not need to include sequence.h. You need to implement the following function in your submitted code:

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

Problem Description

In the fascinating country of APIO, there lives a young and wise student, Alice. Alice has an insatiable curiosity for solving interesting problems that can challenge her mathematical ability. One day, she ran into difficulties while solving a mysterious problem about a sequence of length $N$ (i.e., $A[0], A[1], \cdots, A[N-1]$), and she could not resist the temptation to explore the answer.

Now, she would like to share some of her findings with you. However, for better understanding, we need the following definitions:

• 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] \cdots A[r]$.

• Define the median set of a non-empty integer sequence $B[0] B[1] \cdots B[k-1]$ as $S(\{B[0], B[1] \cdots B[k-1]\})$. Alice will show how to compute the median set step by step:

  • First, sort the sequence $B[0], B[1], \ldots, B[k-1]$ in non-decreasing order, and denote the sorted sequence as $C[0], C[1], \ldots, C[k-1]$.

  • Then, $S(\{B[0], B[1] \cdots B[k-1]\})=\left\{C\left[\left\lfloor\frac{k-1}{2}\right\rfloor\right], C\left[\left\lceil\frac{k-1}{2}\right\rceil\right]\right\}$.

  • To better understand how $S$ is computed, here are some examples:

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

As a challenging problem, Alice wants to find, for all $(l, r)$ with $(0 \leq l \leq r \leq N-1)$, the maximum value of $\max _{x \in S(l, r)} W(l, r, x)$. Here, $S(l, r)$ represents the median set derived from $A[l] \cdots A[r]$ (as mentioned earlier, $S(A[l], \cdots, A[r])$). Although Alice already has an answer, she needs to check whether it is correct, so she comes to you and hopes you can solve the problem by programming.

Implementation Details

You need to implement the following procedure:

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

• $N$: The length of the sequence $A$.
• $A$: An array of length $N$, which is the sequence $A$ mentioned in the input.
• The function should return an integer, representing the maximum value among all valid $(l, r)$.
• This function is called exactly once.

Input Format

The sample grader reads the input in the following format:

Line $1$: $N$.

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

Output Format

The sample grader prints your answer in the following format:

Line $1$: The return value of sequence.

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

3

Hint

Examples

Sample 1

Consider the following call:

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

The function should return $3$.

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

It is easy to verify that $(0,5)$ has the largest value among all valid pairs $(l, r)$.

Sample 2

Consider the following call:

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

The function should return $2$.

Sample 3

Consider the following call:

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

The function should return $3$.

Constraints

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

Subtasks

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

Translated by ChatGPT 5