Subtask 1

Let's consider two signs with positions ~x~ and ~y~. The relative order of these signs on the signposts is solely determined by whether ~K~ is greater than, less than, or equal to ~\frac{x+y}{2}~. This motivates us to consider the set ~S~ containing all values of ~\frac{x+y}{2}~ where ~x~ and ~y~ are the positions of two different signs. Then, it is clear that the only values of ~K~ that we need to consider are the elements of set ~S~, since for any other value of ~K~, we could move the signpost to the first element of ~S~ which is greater or lower than ~K~ without restricting the signposts that we can make.

Consider a fixed value of ~K~. Let ~a_K~ be the number of unordered pairs of signs such that the average of their positions is equal to ~K~. Then, the number of signposts that can be made is ~2^{a_K}~, since each of the pairs can be ordered either way, and the positions of all other signposts on the signpost are fixed.

At first glance, the answer to the problem appears to be ~\sum_{K \in S} 2^{a_K}~. However, it can be seen that for any two adjacent elements of ~S~, there is exactly one sign that can be made at both positions. Hence, the answer is ~1 + \sum (2^{a_K}-1)~.

For ease of implementation, we can work with only integers if we instead define ~b_x~ as the number of unordered pairs of signs such that the sum of their positions is equal to ~x~. Then, the answer is ~1 + \displaystyle\sum_{x=1}^{10^6} (2^{b_x}-1)~. For subtask 1, it suffices to calculate ~b_x~ naively by looping over all pairs of signs.

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

Subtask 2

Let ~c_x~ be ~1~ if there is a sign at position ~x~, and ~0~ otherwise. Then, it can be seen that ~b_x = \left\lfloor \frac 1 2 \displaystyle\sum_{i=0}^x c_i c_{x-i} \right\rfloor~. Thus, we can efficiently calculate ~b_x~ using FFT.

Time complexity: ~\mathcal{O}(N + \max(p_i) \log(\max(p_i)))~