P8193 [USACO22FEB] Sleeping in Class P

Offline classes have finally resumed, and the cow Bessie is very excited. Unfortunately, Farmer John is a very boring lecturer, so she often falls asleep in class. Farmer John noticed that Bessie was distracted in class. He asked another student in the class, Elsie, to track and record how many times Bessie fell asleep in a given class. There are a total of $N$ classes, and Elsie recorded that in the $i$-th class Bessie fell asleep $a_i$ times. The total number of times Bessie fell asleep across all classes is at most $10^{18}$. Elsie considers herself Bessie’s rival, so she wants FJ to believe that in every class Bessie slept the same number of times—making FJ think this is obviously entirely Bessie’s fault, rather than the fact that FJ is sometimes boring. Elsie can modify the record in only the following two ways: merge the records of two adjacent classes, or split the record of one class into two classes. For example, if $a=[1,2,3,4,5]$, then if Elsie merges the records of the second and third classes, the record becomes $[1,5,4,5]$. If Elsie then continues by splitting the record of the third class into two classes, the record could become $[1,5,0,4,5]$, $[1,5,1,3,5]$, $[1,5,2,2,5]$, $[1,5,3,1,5]$, or $[1,5,4,0,5]$. Given $Q$ candidate numbers $q_1,\ldots,q_Q$ that Bessie dislikes the most, for each number, please help Elsie compute the minimum number of operations she needs so that all numbers in the record become this number.

The first line contains an integer $N$ ($1\le N\le 10^5$). The second line contains $N$ integers $a_1,a_2,\ldots, a_N$ ($1\le a_i\le 10^{18}$). The third line contains an integer $Q$ ($1\le Q\le 10^5$). The next $Q$ lines each contain an integer $q_i$ ($1\le q_i\le 10^{18}$), representing the number Bessie dislikes the most.

For each $q_i$, output the minimum number of operations Elsie needs to make every number in the record equal to $q_i$. If it is impossible to make all numbers equal to $q_i$, output $-1$.

**Sample Explanation** Elsie needs at least $4$ modifications to make all numbers in the record equal to $3$. $$ \begin{aligned} &\ 1\ 2\ 3\ 1\ 1\ 4\\ \rightarrow&\ 3\ 3\ 1\ 1\ 4\\ \rightarrow&\ 3\ 3\ 1\ 5\\ \rightarrow&\ 3\ 3\ 6\\ \rightarrow&\ 3\ 3\ 3\ 3\\ \end{aligned} $$ Elsie cannot make all numbers in the record equal to $5$, so the output is $-1$. This is correct. **Constraints** - For testdata groups $2\sim 4$, $N,Q\le 5000$. - For testdata groups $5\sim 7$, all $a_i$ are at most $10^9$. - For testdata groups $8\sim 26$, there are no additional constraints. Translated by ChatGPT 5