5000ms的时限，还挺长的。算法是DP。
思路是找到ans[1..n]的结果，然后Query就容易做了。问题是怎么DP？
考虑：
1 1 2 3 4 4 5w=1: 7， 7 = 1 * 7
w=2: 10，10 = |{1，1}|+|{1，2}|+|{2，3}|+|{3，4}|+|{4，4}|+|{4，5}|=1+2+2+2+1+2=10
w=3: 12, 12 = |{1，1, 2}|+|{1，2, 3}|+|{2，3, 4}|+|{3，4, 5}|+|{4，4, 5}|
...
观察w=3如何在w=2的基础上求得，首先需要减去|{4，5}|，然后考虑2，3，4，5，5（每个集合的最后一个数）是否distinct。
因此，O(n^2)是可解得。不过n的范围是1e6,肯定超时。
那么，简化思路，分成三个部分。
1. ans[n-1];
2. 后k（[1..n]）个数中，distinct的数目可以在O(n)内求得。
3. 而考虑a[w..n]是否对数量增加1，可以换个思路考虑。
考虑1 1 2 3 4 4 5中的3，因为前面没有出现3，因此w=[1..4]时，这个3都会提供增量1。
考虑1 3 2 3* 4 4 5中的3*，因为前面有个3，两者间距2，因此w=[1..2]时，这个3会提供增量1。
可见弄个delta数组，两个O(n)循环可以确定针对w=[1..n]时，这个增量delta是多少。
最后合成一下就可以了。
/* 4455 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = 1e6+;
int a[maxn], b[maxn];
int pre[maxn];
__int64 delta[maxn], ans[maxn];
bool mark[maxn]; int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, q, x;
int l, tmp;
int i, j, k; while (scanf("%d", &n)!=EOF && n) {
for (i=; i<=n; ++i) {
scanf("%d", &a[i]);
++a[i];
}
memset(delta, , sizeof(delta));
memset(pre, , sizeof(pre));
memset(mark, , sizeof(mark)); // handle last i number
for (i=n,j=; i>; --i,++j) {
if (mark[a[i]]) {
b[j] = b[j-];
} else {
b[j] = b[j-]+;
mark[a[i]] = true;
}
}
// handle pre
for (i=; i<=n; ++i) {
l = i - pre[a[i]];
// [1, l]++
delta[]++;
delta[l+]--;
pre[a[i]] = i;
}
ans[] = n;
for (i=; i<=n; ++i) {
delta[i] += delta[i-];
ans[i] = ans[i-] + delta[i] - b[i-];
} scanf("%d", &q);
while (q--) {
scanf("%d", &x);
printf("%I64d\n", ans[x]);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}