It is highly encouraged for you to attempt the problem first, and only use this editorial if you are completely stuck. You'd be surprised how far you can get with sheer persistence!

Note: You should read a previous hint before a later one so as to not miss any definitions or important details.

Subtask 1

Hint 1 Answer

The number of trailing zeroes in a positive integer ~x~ is maximum ~k~ such that ~10^k~ divides ~x~ evenly. The number ~10~ can be split into its prime factors, ~2~ and ~5~, so ~k~ is the minimum of the exponents on ~2~ and ~5~ in the prime factorization of ~x~.

We can write this more compactly with p-adic valuation as ~\min(\nu_2(x),\nu_5(x))~. Using the property that ~\nu_p(xy) = \nu_p(x) + \nu_p(y)~, the number of leading zeroes in the product of the subarray from index ~l~ to ~r~ is $$\displaystyle \min\big(\nu_2(a_l) + \nu_2(a_{l+1}) + \dots + \nu_2(a_r), \nu_5(a_l) + \nu_5(a_{l+1}) + \dots + \nu_5(a_r)\big)$$ To precompute the values of ~\nu_2(a_i)~ and ~\nu_5(a_i)~ for all ~i~, we can use a while loop that counts the number of times we can divide ~a_i~ by ~2~ until it is no longer divisible by ~2~, and a similar while loop for ~5~. The maximum number of times that this while loop will run for a single number is given by ~\lfloor \log_2(\max(a_i)) \rfloor = \lfloor \log_2(10^9) \rfloor = 29~, so speed is not a concern.

Hint 2

Is there a faster way to find the sum of ~\nu_2(a_i)~ and ~\nu_5(a_i)~ in a subarray without looping through it?

Hint 2 Answer

After precomputing ~\nu_2(a_i)~ and ~\nu_5(a_i)~ for all ~i~, we can use prefix sum arrays to find the sum of ~\nu_2(a_i)~ or ~\nu_5(a_i)~ in a subarray in ~\mathcal{O}(1)~ time.

Implementation

First, we precompute ~\nu_2(a_i)~ and ~\nu_5(a_i)~ for all ~i~. Since ~1 \le N \le 5000~ in this subtask, looping through all subarrays is feasible. We can use prefix sum arrays to quickly calculate the sums of ~\nu_2(a_i)~ and ~\nu_5(a_i)~ in each subarray and take the minimum out of the two.

More formally, define ~c_2[i] = \nu_2(a_1) + \nu_2(a_2) + \dots + \nu_2(a_i)~ and ~c_5[i] = \nu_5(a_1) + \nu_5(a_2) + \dots + \nu_5(a_i)~, and ~c_2[0] = c_5[0] = 0~. Thus, ~c_2~ and ~c_5~ are the prefix sum arrays of ~\nu_2(a_i)~ and ~\nu_5(a_i)~, respectively. The answer is given by $$\displaystyle \sum_{0 \le l < r \le N}\min\big(c_2[r] - c_2[l], c_5[r] - c_5[l]\big)$$ Time Complexity: ~\mathcal{O}(N\log(\max(a_i)) + N^2)~

Subtask 2

Hint 1

The ~\min~ function in our sum is difficult to optimize. Is there way to break ~\min(x,y)~ into two pieces which are easier to calculate?

Hint 1 Answer

The ~\min~ function can be broken into two pieces: $$\displaystyle \min(x,y) = \frac{1}{2}\big((x + y) - |x - y|\big)$$ Thus, we can rewrite our desired sum into two separate sums: $$\displaystyle \begin{align*} & \sum_{0 \le l < r \le N}\min(c_2[r] - c_2[l], c_5[r] - c_5[l]) \\ \\ = & \sum_{0 \le l < r \le N} \frac{1}{2}\bigg(\big(c_2[r] - c_2[l] + c_5[r] - c_5[l]\big) - \Big|\big(c_2[r] - c_2[l]\big) - \big(c_5[r] - c_5[l]\big)\Big|\bigg) \\ \\ = & \frac{1}{2} \left[\left(\sum_{0 \le l < r \le N} c_2[r] - c_2[l] + c_5[r] - c_5[l]\right) - \left(\sum_{0 \le l < r \le N} \Big|\big(c_2[r] - c_2[l]\big) - \big(c_5[r] - c_5[l]\big)\Big|\right)\right] \end{align*} $$

Hint 2

Group the terms in the first sum by index: $$\displaystyle \begin{align*} & \sum_{0 \le l < r \le N} c_2[r] - c_2[l] + c_5[r] - c_5[l] \\ \\ = & \sum_{0 \le l < r \le N} (c_2[r] + c_5[r]) - (c_2[l] + c_5[l]) \end{align*} $$ How many times do the contributions from a certain index ~i~ get added (or subtracted) in this sum? Can we use this to get rid of the summation through pairs ~(l,r)~?

Hint 2 Answer

We can define a single contribution from index ~i~ to be ~c_2[i] + c_5[i]~. We can consider two cases, one where ~i~ is the "~r~" in the sum, and one where ~i~ is the "~l~".

Every time ~i~ is the right endpoint in the sum, ~r~, its contribution is added to the sum. The number of times this happens is the number of possible ~l~ which could have their corresponding ~l~ equal to ~i~, which is ~\big|[0,i-1]\big| = i~. Thus, the total contribution from this case is ~\big(c_2[i] + c_5[i]\big) \cdot i~.

Every time ~i~ is the left endpoint in the sum, ~l~, its contribution is subtracted from the sum. The number of times this happens is the number of possible ~r~ which could have their corresponding ~l~ equal to ~i~, which is ~\big|[i+1,N]\big| = N - i~. Thus, the total contribution from this case is ~-\big(c_2[i] + c_5[i]\big) \cdot (N - i)~.

Adding these together to find the total contribution of index ~i~, we get $$\displaystyle \begin{align*} & \big(c_2[i] + c_5[i]\big) \cdot i~ - \big(c_2[i] + c_5[i]\big) \cdot (N - i) \\ \\ = & \big(c_2[i] + c_5[i]\big) \cdot (2i - N) \end{align*} $$ This gives us a neat expression for the contribution of a certain index ~i~ to the sum. We can rewrite the sum over indices ~i~ instead of pairs ~(l,r)~ now: $$\displaystyle \begin{align*} & \sum_{0 \le l < r \le N} c_2[r] - c_2[l] + c_5[r] - c_5[l] \\ \\ = & \sum_{i=0}^N \big(c_2[i] + c_5[i]\big) \cdot (2i - N) \end{align*} $$

Hint 3

The absolute value bars in our second sum are difficult to optimize. However, remember that ~|x - y| = |y - x|~. What does this mean we can do to our sum to make it easier to calculate?

Hint 3 Answer

Again, we group terms by index. $$\displaystyle \begin{align*} & \sum_{0 \le l < r \le N} \Big|\big(c_2[r] - c_2[l]\big) - \big(c_5[r] - c_5[l]\big)\Big| \\ \\ = & \sum_{0 \le l < r \le N} \Big|\big(c_2[r] - c_5[r]\big) - \big(c_2[l] - c_5[l]\big)\Big| \end{align*} $$ Since ~|x - y| = |y - x|~, swapping two adjacent indices ~i~ and ~i+1~ would have no effect on the sum. Swapping two adjacent indices can be done repeatedly to slowly transform the array into any permutation we want, and the sum will still be the same.

Thus, we can sort the indices by ~c_2[i] - c_5[i]~ and be sure that ~\big(c_2[r] - c_5[r]\big) \ge \big(c_2[l] - c_5[l]\big)~, which allows us to completely remove the absolute value bars from our sum.

More formally, define ~\sigma_i~ as a permutation of ~[0,N]~ that is sorted by ~c_2[i] - c_5[i]~. $$\displaystyle \begin{align*} & \sum_{0 \le l < r \le N} \Big|\big(c_2[r] - c_2[l]\big) - \big(c_5[r] - c_5[l]\big)\Big| \\ \\ = & \sum_{0 \le l < r \le N} \big(c_2[\sigma_r] - c_2[\sigma_r]\big) - \big(c_2[\sigma_l] - c_2[\sigma_l]\big) \end{align*} $$ Finally, we can optimize the calculation of this sum with the same trick used for the other piece of the original sum.

Implementation

Again, we precompute ~\nu_2(a_i)~ and ~\nu_5(a_i)~ for all ~i~, and build prefix sum arrays, ~c_2~ and ~c_5~, so that ~c_2[i] = \nu_2(a_1) + \nu_2(a_2) + \dots + \nu_2(a_i)~ and ~c_5[i] = \nu_5(a_1) + \nu_5(a_2) + \dots + \nu_5(a_i)~, and ~c_2[0] = c_5[0] = 0~.

Then, we can create two arrays, ~s[i] = c_2[i] + c_5[i]~ and ~d[i] = c_2[i] - c_5[i]~. Sort ~d~ in ascending order.

The answer is given by $$\displaystyle \frac{1}{2}\sum_{i=0}^N (s[i] - d[i]) \cdot (2i - N)$$ Time Complexity: ~\mathcal{O}(N\log(\max(a_i)) + N\log N)~