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.