Codeforces Round 988 (Div. 3) -- My Editorial
Let's maintain a $\mathtt{map}$ to count the frequency of each $a[i]$ , this can be done in $O(n)$ , Now each element will be counted twice $\displaystyle \left \lfloor \frac{n}{2} \right \rfloor$
according to the definition of floor division , Formally the answer is
$$\displaystyle \sum \left \lfloor \frac{x}{2} \right \rfloor$$
For each $x \in a$ and every $x$ is distinct . Complexity is $O(n)$ time.
Notice that the grid contains the dimensions of it , thus the real grid size is $k-2$ , thus we want to find any pair in the grid such $\displaystyle (x,\frac{k-2}{x})$
exists , We can get every divisor of $k-2$ in $O(\sqrt{k-2})$ time , so we get the divisors and search in the array if such pair exists , this can be done with map ,
however in contest , both $\mathtt{dict}$ and $\mathtt{defaultdict}$ fails on test 4 TLE (intended by evil cry to leave python) , btw using $\mathtt{Counter}$ works
I wasn't aware of $\mathtt{Counter}$ so I moved to C++ $\color{green}{\mathtt{AC}}$ .
Complexity is $O(k)$.
Handled cases of $n<8$ first
$n \le 4 : -1$
$5 \le n \le 7$ : I generated by brute force and select one for each .
$n \ge 8$ : The construction is simple
put all evens except $8$ in first and $8$ lastly and then odd numbers thus we've that each number
is divisble by $2$ (composite) except the median which is $8+1=3^2$ which is also composite .
Complexity is $O(n)$.