If there is a contiguous section of at least three plants that appears twice, then there is also a contiguous section of exactly two plants that appears twice. Thus, we may restate the problem as:

Find the largest palindromic array containing integers between ~1~ and ~K~, such that no subarray of length ~2~ appears twice.

Subtask 1

Since the array is palindromic, we may focus only on deciding the first half of the array. Observe that there cannot be two equal adjacent elements in the first half, since this would imply that this pair of equal adjacent elements also appears in the second half. Thus, there cannot be two equal adjacent elements, with the exception that if the array has an even length, then the middle two elements can be equal. Also, if ~[x, y]~ appears as a subarray in the first half, then ~[y, x]~ cannot appear as a subarray in the first half.

It now becomes clear that the goal is to generate an array such that every pair of elements appears consecutively (in either order) in the first half at most once, and no two adjacent elements are equal; then, we will concatenate this array with its reversed self. For example, if we generate the first half of the array as ~[1, 2, 3, 1]~, then our final array is ~[1, 2, 3, 1, 1, 3, 2, 1]~.

Each pair of consecutive elements in the first half must be one of the ~\frac{K(K-1)}{2}~ possible unordered pairs of elements. Hence, the length of the first half cannot exceed ~\frac{K(K-1)}{2}+1~. We will show by construction that this is always possible when ~K~ is prime.

When ~K = 2~, we can simply let the first half be ~[1, 2]~.

Otherwise, we can perform the following procedure, considering elements equivalent modulo ~K~:

Start with the array ~[1]~, and initialise ~cur = 1~.

Then, for all ~x~ in ~[1, \frac{K-1}{2}]~, we will increase ~cur~ by ~x~ and then append ~cur~ to the array ~K~ times.

For example, when ~K = 5~, we will generate the array ~[1, 2, 3, 4, 5, 1, 3, 5, 2, 4, 1]~.

This works because for a fixed value of ~x~, we will generate all subarrays of length ~2~ where the first elements is congruent to ~x~ less than the second element, modulo ~K~. This relies on the fact that the GCD of a prime number and any whole number less than it is ~1~.

Then, for all pairs of different integers ~p~ and ~q~, if ~q-p \le \frac{K-1}{2}~, ~[p, q]~ will be a subarray of the generated array. Otherwise, ~(p-q)~ mod ~K \le \frac{K-1}{2}~, so ~[q, p]~ will be a subarray of the generated array.

Time complexity: ~\mathcal{O}(K^2)~

Subtask 2

Consider a complete graph with ~K~ nodes, labelled from ~1~ to ~K~, that is, there is an undirected edge between every pair of nodes. Then, observe that the first half is equivalent to a trail on the graph (i.e. a walk with no repeating edges). Since we want to find the maximum length trail, ideally, we want to find an Eulerian trial (a trail which traverses every edge).

When ~K~ is odd, every node has an even degree, so an Eulerian trail can easily be found.

However, when ~K~ is an even number greater than ~2~, there are more than ~2~ nodes with an odd degree, so an Eulerian trail does not exist. Our goal is now to delete the fewest edges such that the graph becomes Eulerian.

We require either ~0~ or ~2~ nodes to have an odd degree, and removing an edge can reduce the number of nodes with an odd degree by at most ~2~. Hence, the lower bound on the number of deleted edges is ~\frac{K}{2}-1~.

However, it is always possible to remove ~\frac{K}{2}-1~ edges to obtain an Eulerian graph. We can simply remove the edge between nodes ~3~ and ~4~, the edge between nodes ~5~ and ~6~, the edge between nodes ~7~ and ~8~, and so on. This will result in only nodes ~1~ and ~2~ having odd degrees.

To find an Eulerian trail, we can run Hierholzer's algorithm. Due to the nature of this graph, it is also possible to run a DFS on the graph, greedily choosing to move to the neighbour with the lowest label such that the current edge is untraversed.

Time complexity: ~\mathcal{O}(K^2)~