Problem G
Multithreading
Dr. Back has recently noticed that Sri has shown up late to his Computer Systems class multiple times. Sri keeps saying he’ll stop doing it on this day or that day, but it hasn’t happened yet. In order to show him just how bad of an idea this is, Dr. Back decided to run an experiment. Instead of teaching a lesson on multithreading, he has decided to perform multithreading on reality itself: he will split every one of these hypothetical end dates into a new timeline and examine them individually.
Let each class throughout the semester have some associated amount of knowledge that Sri would obtain during that class if he didn’t show up late for that class or any future classes. The issue with showing up late for a given class is that the knowledge gained from the previous classes (or the later classes, depending on how you interpret it) is effectively decreased, since the material builds on top of itself. So, if, in some alternate timeline, Sri says that he will keep showing up late until some certain day and then never do it again after that, then all of the knowledge values until and including that day would surely become limited in that timeline as an effect of Sri being late to, and taking in less material from, his classes, which occasionally (luckily for him) causes no decrease at all.
Specifically, given that there are $n$ classes in the semester, we will have a knowledge array $k$ of length $n$ containing the knowledge values from each class. If Sri says that he will keep showing up late until class $c_{end}$, then for the timeline where that is true, we will have a new knowledge array $k_{new}$ with the following modifications: all of the days after $c_{end}$ will be unaffected (i.e., $k_{new_{c}} := k_c$), and for each class $c \in \{ 1, 2, \ldots , c_{end}\} $, $k_{new_{c}}$ will be set to the minimum knowledge across all knowledge values for the classes between the current class $c$ and $c_{end}$, inclusive (i.e., $k_{new_{c}} := min(k_c, k_{c+1}, k_{c+2}, \ldots , k_{c_{end}})$).
By creating a new timeline for each $c_{end}$ value that Sri whimsically threw out, Dr. Back can analyze the $k_{new}$ array corresponding to that timeline and show Sri how much it reduces the amount he learns; he does this by simply computing the total knowledge, $t$, gained in that timeline (i.e., the sum of all knowledge values in $k_{new}$). Your task is to find $t$ for each given $c_{end}$.
Input
The first line contains an integer $n$ ($1 \leq n \leq 200,000$), which is the length of the knowledge array. The second line contains $n$ integers, which are the elements of the knowledge array $k$ ($1 \leq k_{c} \leq 10^{9}$) with spaces in between them. The third line contains an integer $q$ ($1 \leq q \leq 200,000$), the number of different $c_{end}$ values Sri has stated to Dr. Back. The fourth line contains $q$ space-separated $c_{end}$ values ($1 \leq c_{end} \leq n$).
Output
For each $c_{end}$, output the corresponding $t$. The outputs for each query should be separated by spaces.
Sample Case 1 Explanation
If Sri shows up late for the last time on day $4$, then $k_{new}$ would look like $[2, 4, 4, 4, 7, 5]$, whose sum is $26$. Similarly,
$c_{end} = 2 \Rightarrow k_{new} = [2, 4, 5, 4, 7, 5] \Rightarrow t = 27$
$c_{end} = 6 \Rightarrow k_{new} = [2, 4, 4, 4, 5, 5] \Rightarrow t = 24$
$c_{end} = 3 \Rightarrow k_{new} = [2, 4, 5, 4, 7, 5] \Rightarrow t = 27$
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 4 5 4 7 5 4 4 2 6 3 |
26 27 24 27 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 5 3 4 3 2 9 7 5 3 9 5 6 6 6 2 12 3 1 4 |
54 59 38 59 61 58 |
