It can be proved that \(f(A)\) equals the product of the top (greatest) 2 elements of \(A_i(1 \le i \le N-1)\) plus the maximum element behind the latter of the top 2. (Tiebreak in ascending order of \(i\).)

Accepting this fact, we perform counting. Let the values of top 2 be \(x\) and \(y\). Then, only the sequences that can be expressed in the following form satisfy the condition for \(A\).

• Any number of values between \(1\) and \(\min(x-1,y-1)\), inclusive
• \(x\)
• Any number of values between \(1\) and \(\min(x,y-1)\), inclusive
• \(y\)
• Any number of values between \(1\) and \(\min(x,y,K-xy)\), inclusive
• One value between \(1\) and \(K-xy\), inclusive

The number of sequences of this form can be found in \(\mathrm{O}(\log N)\) using the Bostan-Mori method, etc. The number of pairs \((x,y)\) can be kept at \(\mathrm{O}(K \log K)\), so the time complexity is \(\mathrm{O}(K \log K \log N)\).

We prove the fact used above. Let the top 2 elements be \(A_i\) and \(A_j\), and let one of the elements that takes the maximum value among those behind \(A_j\) be \(A_k\). Then, suppose we can get a better solution \(A_x A_y + A_z\).

• When $j \le y$
We can say $A_iA_j \le A_xA_y$ and $A_k \le A_z$, which is a contradiction.
• When $y < j$
If $j < z$, we can say $A_iA_j \le A_xA_y$ and $A_k \le A_z$, which is a contradiction. Also, since $A_j$ is maximum among $A_1,A_2,\dots,A_j$ except for $A_i$, we know that $z$ is $i$ or $j$.
• When $z = i$
From $A_x,A_y < \min(A_i,A_j)$, we have $A_xA_y \le (A_i-1)(A_j-1) = A_iA_j - A_i - A_j + 1 \le A_iA_j - A_i$, so $A_xA_y + A_z \le A_iA_j - A_i + A_i \le A_iA_j < A_iA_j + A_k$, which is a contradiction.
• When $z = j$
From $A_x,A_y < \min(A_i,A_j-1)$, we have $A_xA_y \le A_i(A_j-1) = A_iA_j - A_j$, so $A_xA_y + A_z \le A_iA_j - A_j + A_j \le A_iA_j < A_iA_j + A_k$, which is a contradiction.

Thus, the fact is shown.