Whats the need to have difficult problem statements? For most English isn't the first language and as far as i know contests are supposed to judge problem solving skill and not english comprehension. If you cannot dilute the story to simple sentence, stick to directly giving the main problem.

Hello everyone, below is a proof for yesterday's Div2 D problem. Since many of us reached the solution intuitively, this will provide insight into the mathematics behind it.

Proof for the Permutation Construction

Our Construction

We construct a permutation with the following pattern: [f, f-1, f+1, f-2, f+2, ..., 1, 2f-1, 2f, 2f+1, ...]

where f is a prime number such that f ≥ n/3.

Key Properties

1. The first 2f-1 elements follow an alternating pattern around f
2. The remaining elements (2f, 2f+1, ..., n) are placed in ascending order

Proof of Correctness

Let's analyze the values of c_i = ⌈(p₁ + p₂ + ... + pᵢ)/i⌉ for our construction.

Consider the first 2(k+1) elements of our permutation (where k is the number of pairs in our alternating pattern).

The sum of these elements is: f + (f-1) + (f+1) + (f-2) + (f+2) + ... + (f-k) + (f+k) = f + [f-1 + f+1 + f-2 + f+2 + ... + f-k + f+k] = f + [2f·k - (1+2+...+k) + (1+2+...+k)] = f + 2f·k = f(1+2k)

The number of elements is 2k+1+1 = 2(k+1)

Therefore, the average is: f(1+2k)/(2(k+1)) = f(1+2k)/(2k+2) = f(1+2k)/(2(1+k)) = f/2 · (1+2k)/(1+k)

Since k ≥ 0, we know (1+2k)/(1+k) > 1, specifically: (1+2k)/(1+k) = (1+k+k)/(1+k) = 1 + k/(1+k) = 1 + 1/(1+1/k) = 2 - 1/(1+k)

So our average is: f/2 · (2 - 1/(1+k)) = f - f/(2(1+k))

This value is always strictly between f-1 and f (since f/(2(1+k)) < 1 but > 0).

Therefore, ⌈f — f/(2(1+k))⌉ = f for all valid k.

This means that for the first 2f-2 elements of our permutation, c_i = f (which is prime by our choice of f).

Since f ≥ n/3, we have at least 2(n/3)-2 = (2n/3)-2 elements where c_i = f. This is greater than ⌊n/3⌋-1 as required by the problem.

Efficiency

Finding a suitable prime f is efficient using a sieve of Eratosthenes with a reasonable upper limit (35000 in our implementation).

Therefore, the overall solution has a time complexity of O(n) for each test case.