402225: GYM100703 H A lot of work

— And Prince — what games does he play? — Princess looked at Dragon thoughtfully.

— Prince... He has so many different affairs all the time, he has no time for games, — Dragon thought for a moment and added, — Perhaps, that he is busy all the time is a reason why he doesn't want to play games...

Prince does his best to work as effectively as possible. So, some time ago Prince observed, that if he performs the same job during more than one unit of time, his work efficiency decreases conspicuously. For this reason he tries to do different jobs at any two consecutive units of time now.

Prince reports about all the work he does. After doing some kind of job during one unit of time, he paints over a cell on a strip of paper with a marker. One day Dragon took an interest what do all those colored squares mean. Prince clarified that every job corresponds to a color. Unfortunately, the number of markers is limited, so Prince can use the same color for different jobs. Of course, in this case the next job starts after the end of the previous job.

Prince boasted of his methods, and mentioned that he uses, among the other things, a forgetting parameter. The forgetting parameter is an integer k, a maximum allowable distance between two cells of the same color, if these cells are associated with the same job. It is clear, that it is not guaranteed that cells are associated with the same job if distance between cells is not greater than k and they have the same color. But it is guaranteed that every two cells are associated with different jobs if distance between them is greater than k and they have the same color.

Dragon interests what minimum number of different jobs Prince could have done for the last time. Your task is to compute it by a given colored strip and a value of k. For the sake of simplicity we use numbers instead of colors.

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of colored cells.

The second line contains sequence of numbers c₁, c₂, ..., c_n (1 ≤ c_j ≤ 10⁵) — the description of colored cells. The same numbers correspond to the same colors and vice versa.

The third line contains integer q (1 ≤ q ≤ 10⁵) — the number of queries.

The fourth line contains integers k₁, k₂, ..., k_q (1 ≤ k ≤ n) — the values of forgetting parameter, for every of which you should compute minimum possible number of jobs that Prince could have done during n units of time.

Print q integers d_j (j = 1, 2, ..., q) in the first line. Number d_j is the minimum possible number of jobs that Prince could have done for jth value of forgetting parameter.

6
1 1 1 1 1 1
5
1 2 3 4 5

3 2 2 2 1 

15
3 2 1 3 4 8 2 1 1 3 3 1 4 6 2
6
7 3 10 5 4 6

10 12 7 10 11 10