A cache of every size

caching prefix sums range queries offline queries networks

How much memory should a web server cache get? To decide, you want to know for each possible size how many of yesterday’s requests would have done without the disk. The cache works by the LRU rule: it holds k pages, and when short of room the one that has gone longest without being accessed is thrown out; the cache is empty at first. There is one request log, and many sizes to check.

One of the tests is the first 100,000 successful requests to the Kennedy Space Center server on 13 July 1995, with pages replaced by numbers, and sizes from 1 to 3000.

Input

The first line holds n (1 ≤ n ≤ 100,000). The second holds n page numbers in order of request, each from 1 to 10⁹. The third holds q (1 ≤ q ≤ 100,000), the fourth q cache sizes k (1 ≤ k ≤ n).

Output

For each size, a line with the number of hits of a cache of that size over the whole log.

Examples

Example 1

Input

12
1 2 3 4 1 2 5 1 2 3 4 5
5
1 2 3 4 5

Output

Example 2

Input

Output

2
3

Limits

Time · Python: 6000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Running the log through a cache of each size is O(n) per size and O(nq) in all. Caches of different sizes behave differently, but not arbitrarily: what does a cache with k places hold compared with a cache with k + 1 places?

2Hint 2

A cache with k places always holds the k most recently accessed pages (or all of them, if there were fewer distinct ones). So an access hits a cache with k places exactly when, since the previous access to this page, fewer than k distinct other pages were asked for. This number is the stack distance, and it does not depend on k.

3Hint 3

It remains to count quickly how many distinct pages were asked for between two accesses to one page. Mark with a one the moment of the last access to each page: the distinct pages asked for after moment p are the marks to the right of p.

4The idea

One pass over the log with a Fenwick tree over moments of time. The tree has a one at the moment of the last access to each page seen so far. On an access at moment t to a page last asked for at moment p, the stack distance equals the number of ones to the right of p: all pages seen minus the prefix sum up to p inclusive. Record the distance in a histogram, and move the one from p to t. A cache with k places hits on all accesses with distance less than k, so the answer is the cumulative sum of the histogram.

5Walkthrough

The first access to a page is a miss at any size; it does not go into the histogram but only adds a one and increases the counter of pages seen. Page numbers up to a billion need no compression: the dictionary “page → moment of last access” stores only those seen. After the pass hits[k] = hits[k − 1] + at[k − 1], and each question is one lookup.

The distance can also be computed as a sum over the interval (p, t), that is, a difference of two prefixes; subtracting from the number of pages seen saves one descent of the tree.

5+Solution

6Complexity

O(n log n + q) time and O(n) memory. Mattson’s simple stack, a list of pages in order of access, gives the same distances, but finding a page in it takes as many steps as the distance: O(n·d). On the NASA log that is a little over a hundred steps per request, and in the fourth test, where thirty thousand pages are asked for at random, tens of thousands.

7Common mistakes

A simulation for each size. O(nq): the fourth test has a hundred thousand sizes.
A stack on a list. Correct, but O(n·d): where distances are large, it is billions of steps.
Counting all requests in the distance rather than distinct pages. If another page was asked for ten times between two accesses to a page, a cache with two places is enough: the distance is one.
The first access in the histogram. Its distance is infinite: it hits at no size. In the first example a cache with 5 places catches 7 accesses of 12, not 12.

Algorithms behind it

DS Data structure LRU cache A dictionary plus a doubly linked list: get and put in O(1), and out goes the one accessed longest ago. O(1) per get and put 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems