sequence (APIO contest)
Time limit: 1.5 seconds | Memory limit: 2048 MB | Task type: batch
Algorithms: line sweep, data structures, segment tree, binary search

![image](_page_0_Picture_0.jpeg)

# Sequence

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} [A[i] = x]$, i.e., the number of occurrences of $x$ in $A[l] \dots A[r]$.
- Define the set of **medians** of a non-empty integer sequence $B[0], B[1], \dots, B[k-1]$ as $S(\{B[0], B[1], \dots, B[k-1]\})$, and in the following 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 maximum value of $\max_{x \in S(l,r)} W(l, r, x)$, where $0 \le l \le r < N - 1$, as it poses a challenging task. The term $S(l, r)$ represents the set of medians derived from $A[l] \dots A[r]$ (as 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:

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

- $N$: the length of sequence $A$.
- $A$: 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.

## Examples

#### Example 1

Consider the following call:

```c++
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:

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

This procedure should return 2.

#### Example 3

Consider the following call:

```c++
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 $\forall 0 \le i < x, A[i] \le A[i+1]$ and $\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.

Starter code:
sequence.cpp: #include "sequence.h"

#include <vector>

int sequence(int N, std::vector<int> A) {
  return 0;
}

grader.cpp: #include "sequence.h"

#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}

sequence.h: #include <vector>

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


Grader code:
grader.cpp: #include "sequence.h"

#include <cassert>
#include <cstdio>

// BEGIN SECRET
#include <string>
// END SECRET
#include <vector>

int main() {
  // BEGIN SECRET
  {
    std::string in_secret = "8wq90di9812978rqwiok0k0o21klklm21oiwi121";
    std::string out_secret = "nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp";
    char secret[1000];
    assert(1 == scanf("%s", secret));
    if (std::string(secret) != in_secret) {
      printf("%s\n", out_secret.c_str());
      printf("SV\n");
      fclose(stdout);
      return 0;
    }
  }
  // END SECRET
  int N, K;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  // BEGIN SECRET
  {
    std::string out_secret = "nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp";
    printf("%s\n", out_secret.c_str());
    printf("OK\n");
  }
  // END SECRET
  printf("%d\n", result);
  return 0;
}

sequence.h: #include <vector>

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


Setup script:

Evaluation script: