Ice Growth

Interview

Time limit1.5sMemory limit1024 MB

Summary

Ice thickness changes each day by a_i/5, never dropping below zero; for each person, count the days the thickness reaches their required minimum.

Level: Medium4 of 10
Topics: Array, Prefix sum, Binary search, Sorting
Solved: No attempts yet

Problem

Ice growth depends on temperature. A rule of thumb is that every $5$ degrees of frost (on average over a $24$ -hour period) contributes $1$ cm of ice growth, while every $5$ degrees above zero removes $1$ cm of ice. For example, if there are three days with average temperatures of $-3$ , $1$ and $-7$ degrees Celsius, there will be a total of $3 - 1 + 7 = 9$ degrees of frost and thus $1.8$ cm of ice growth at the end of day $3$ . Of course, the ice thickness cannot be negative. If there is enough ice, people can skate on it. The required ice thickness depends on the person, since different people have different perceptions of safety.

There is currently no ice, but the weather report for the next $n$ days has just come in, and a group of $k$ people wants you to figure out how many of these days they can skate on the ice at the end of the day.

Input

The input consists of:

One line containing two integers, $n$ ( $1\leq n \leq 10^5$ ) the number of days and $k$ ( $1 \leq k \leq 10^5$ ) the number of people.
One line with $n$ integers $a\_1, \ldots, a\_n$ ( $-10^6 \leq a\_i \leq 10^6$ for all $i$ ), the average temperature on day $i$ .
One line with $k$ integers $b\_1, \ldots, b\_k$ ( $1 \leq b\_j \leq 10^6$ for all $j$ ), the required minimal ice thickness in cm before person $j$ can skate on the ice.

Output

Output a line with $k$ integers $c\_1, \ldots, c\_k$ , where $c\_j$ is the number of days that person $j$ can skate on the ice at the end of the day.

Examples2

Example 1
Input
```
3 2
-3 1 -7
1 2
```
Expected output
```
1 0
```
Example 2
Input
```
5 3
-5 -5 15 -5 -5
1 2 3
```
Expected output
```
4 2 0
```