Problem.$$$\newline$$$ Given $$$n$$$ $$$\le$$$ $$$3 \cdot 10^{5}$$$ white boards, lenght $$$i$$$ is $$$a_i \le 3 \cdot 10^5$$$, and $$$t$$$ $$$\le$$$ $$$5$$$ red boards, lenght $$$i$$$ is $$$b_i \le 3 \cdot 10^5$$$. Polycarp wants to assemble a fence with exactly one red and some (maybe 0) white boards. A fence is good if before the red board all white boards strictly increase, and after it they strictly decrease and every white strictly less than red board. More formally let $$$l_1$$$, $$$l_2$$$, ..., $$$l_m$$$ lenghts of boards, then the conditions must be met:

• The fence must use exactly one red board. (let it be in at position $$$j$$$);
• For every $$$i \in [1, j - 1]$$$ $$$l_i \lt l_{i+1}$$$;
• For every $$$i \in [j, m - 1]$$$ $$$l_i \gt l_{i+1}$$$.

Two fences are considered distinct if their length arrays are distinct. Polycarp will construct his fence as follows: he places all the planks from left to right on the ground (height 0), without gaps, that is, these planks form a polygon: $$$\newline$$$ Example: a fence with length array [3,5,4,2,1]. The second plank is red. The perimeter of this fence is 20.$$$\newline$$$ Polycarp is only interested in fences with $$$q \le 3 \cdot 10^{5}$$$ perimeters. For each $$$Q_i \le 12 \cdot 10^{5}$$$ (the required perimeter), calculate the number of different fences with the perimeter of $$$Q_i$$$.$$$\newline$$$ Solution.$$$\newline$$$ Since the number of red boards is small, let's fix a red board, let it at index $$$i$$$ in array $$$b$$$, let the number of white boards be $$$cnt$$$, and then the perimeter of the fence is $$$2 \cdot (b_i + cnt + 1)$$$. We introduce a polynomial equal to the product of the following expressions over each possible length (this will be $$$l$$$) of the white board:

• If the number of occurrences of $$$l$$$ in $$$a = 1$$$, we multiply the polynomial by $$$1 + 2x$$$ (if we add a board of length $$$l$$$ to the fence, then there are 2 options where to put it: to the left of the red one and to the right, also 1 will be added to $$$cnt$$$, otherwise the unit will not affect the answer),
• If the number of occurrences of $$$l$$$ in $$$a \gt 1$$$, we multiply the polynomial by $$$1 + 2x + x^2$$$ (now the board $$$l$$$ can be added in one way as in the first case and added from both sides, which will bring $$$cnt$$$ to 2).

Ultimately, we obtain a polynomial $$$P(x)$$$. In this case, the answer to the $$$j$$$-th query (for a fixed $$$i$$$) is equal to the coefficient of $$$P(x)$$$ at $$$x^{\frac{Q_i}{2} - b_i - 1}$$$ (hereinafter, the coefficient of $$$x^k$$$ will be denoted as $$$P(x)[x^k]$$$). If $$$\alpha$$$ is the number of occurrences of the first term in $$$P(x)$$$, and $$$\beta$$$ is the number of occurrences of the second term in $$$P(x)$$$, then $$$P(x) = (1 + 2x)^{\alpha} \cdot (1 + x)^{2\beta}$$$.$$$\newline$$$ Thus, we obtain a solution in $$$O(nt \log n)$$$ if we calculate $$$P(x)$$$ using the FFT.$$$\newline$$$ We remove the FFT.$$$\newline$$$ Let $$$P(x) = f_{n}x^n + f_{n-1}x^{n-1} + ... + f_{1}x + f_0 = (1 + 2x)^{\alpha} \cdot (1 + x)^{2\beta}$$$$$$\newline$$$ $$$P'(x) = nf_{n}x^{n-1} + (n-1)f_{n-1}x^{n-2} + ... + 2f_{2}x + f_1 = \frac{2\alpha P(x)}{1 + 2x} + \frac{2\beta P(x)}{1 + x}$$$$$$\newline$$$ $$$\frac{P'(x)}{P(x)} = \frac{2(\alpha + \beta) + 2(\alpha + 2\beta)x}{1 + 3x + 2x^2} \Rightarrow P'(x) \cdot (1 + 3x + 2x^2) = P(x) \cdot (2(\alpha + \beta) + 2(\alpha + 2\beta)x)$$$$$$\newline$$$ $$$A(x) = P'(x) \cdot (1 + 3x + 2x^2)$$$$$$\newline$$$ $$$A(x)[x^k] = P'(x)[x^k] \cdot 1 + P'(x)[x^{k-1}] \cdot 3 + P'(x)[x^{k-2}] \cdot 2 = (k+1)f_{k+1} + 3kf_{k} + 2(k-1)f_{k-1}$$$$$$\newline$$$ $$$B(x) = P(x) \cdot (2(\alpha + \beta) + 2(\alpha + 2\beta)x)$$$$$$\newline$$$ $$$B(x)[x^k] = P(x)[x^k] \cdot 2(\alpha + \beta) + P(x)[x^{k-1}] \cdot 2(\alpha + 2\beta) = 2(\alpha + \beta)f_k + 2(\alpha + 2\beta)f_{k-1}$$$$$$\newline$$$ $$$A(x)[x^k] = B(x)[x^k] \Rightarrow (k+1)f_{k+1} + 3kf_{k} + 2(k-1)f_{k-1} = 2(\alpha + \beta)f_k + 2(\alpha + 2\beta)f_{k-1} \Rightarrow$$$$$$\newline$$$$$$\Rightarrow f_{k+1} = \frac{(2\alpha + 2\beta - 3k)f_k + (2\alpha + 4\beta - 2k + 2)f_{k-1}}{k+1}$$$$$$\newline$$$ As a result, we obtained a recurrence formula for $$$f_k$$$, $$$f_0 = 1, f_1 = 2(\alpha + \beta)$$$. We also need to check the special cases: $$$\alpha = 0$$$ or $$$\beta = 0$$$. Now the solution runs in $$$O(nt)$$$.$$$\newline$$$ Acknowledgements.$$$\newline$$$ Thanks to teraqqq for the trick shown above.$$$\newline$$$ $$$\newline$$$ P.S. I hope that I have not made many mistakes in the translation.