Substrings

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

XXX has an array of length n. XXX wants to know that, for a given w, what is the sum of the distinct elements’ number in all substrings of length w. For example, the array is { 1 1 2 3 4 4 5 } When w = 3, there are five substrings of length 3. They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12

Input

There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a1,a2…an, representing the elements of the array.
Then there is a line with an integer Q, the number of queries. At last Q lines follow, each contains one integer w, the substring length of query. The input data ends with n = 0 For all cases, 0<w<=n<=106, 0<=Q<=104, 0<= a1,a2…an <=106

Output

For each test case, your program should output exactly Q lines, the sum of the distinct number in all substrings of length w for each query.

Sample Input

7 1 1 2 3 4 4 5 3 1 2 3 0

Sample Output

7 10 12

Hint

Source

2012 Asia Hangzhou Regional Contest

提交代码