Competition of sequences (Editorial)

Let $v$ be the input array of numbers. Initialize the pointers i = 0 at the beginning of the array and j = n - 1 at the end of the array. We will count the strength of the sequence in the variable $k$. Initially, set k = 1.

While the pointers $i$ and $j$ do not meet, perform the following actions:

1. Move the pointer $i$ one position to the right if it does not point to the number $k$.

2. Move the pointer $j$ one position to the left if it does not point to the number $k$.

3. If both pointers point to the number $k$, increase $k$ by one and move each pointer one position in the corresponding direction.

After the algorithm completes, the answer will be the value k - 1.

Example

Consider the second test. Initialize the pointers. Move the pointer $i$ to the right and the pointer $j$ to the left until they both point to the number $1$.

Move the pointer $i$ to the right and the pointer $j$ to the left until they both point to the number $2$.

The pointers meet, we stop the algorithm. The answer will be the value k = 2.

Algorithm realization

Read the input data.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Set the pointers to the start and end of the array $v$.

int i = 0, j = v.size() - 1;

In the variable $k$, we count the strength of the sequence.

k = 1;
while (i <= j)
{

Move the pointer $i$ to the right until it encounters the number $k$.

  if (v[i] != k) i++;

Move the pointer $j$ to the left until it encounters the number $k$.

  if (v[j] != k) j--;

If both pointers point to the number $k$, then increase $k$ by one.

  if (v[i] == k && v[j] == k) k++;
}

Print the answer.

printf("%d\n", k - 1);

Python realization

Read the input data.

n = int(input())
v = list(map(int, input().split()))

Set the pointers to the start and end of the list $v$.

i, j = 0, len(v) – 1

In the variable $k$, we count the strength of the sequence.

k = 1
while i <= j:

Move the pointer $i$ to the right until it encounters the number $k$.

  if v[i] != k:
    i += 1

Move the pointer $j$ to the left until it encounters the number $k$.

  if v[j] != k:
    j -= 1

If both pointers point to the number $k$, then increase $k$ by one.

  if v[i] == k and v[j] == k:
    k += 1

Print the answer.

print(k - 1)