Polices Raided on Town!

There are N shops in a town named “The Worst-Model-Town”. The owner of the i’th shop is A[i]. One day ‘K’ polices raided on these shops. There are some rules for this raid. They are:

Exactly K police must raid there. Each police raids at least one shop.
Every shop must be raided by exactly one police.
The shops which become raided by a police must be consecutive.

For each shop the owners have to pay ‘x’ dollars. But the owners are corrupted in that town. If there is more than one shop which belongs to the same owner and also raided by the same police then, the owner of these shops will pay only for one shop!

Suppose there are 5 shops. Owner of these 5 shops are : 1, 3, 2, 1 and 1. So, the owner of the shops 1, 4, 5 (1-indexing) is named 1, the owner of the shop 2 is named 3 and the owner of the shop 3 is named 2. If only one police raid all these shops, the owner named 1 has to pay only ‘x’(only for one shop) in spite of being owner of three shops in that town. The owner named 2 has to pay ‘x’. The owner named 3 also has to pay ‘x’.

Given information about number of shops, number of police and amount of dollars (that have to pay to the police if his shops are raided by that police) calculate the maximum amount of dollars the polices can earn in total if they raid optimally.

Input

The first line contains an integer N (1 ≤ N ≤ 10000) which is the number of shops in that town.
Second line contains N integers that is A[1], A[2], A[3], … A[N] where A[i] denotes the name of the owner of the i’th shop (1 ≤ A[i] ≤ N).
The third line contains one integer q (1 ≤ q ≤ 100000) which denotes the number of query.
Next q lines contain a query which is in the form x K (1 ≤ x ≤ 100000, 1 ≤ K ≤ min (1000, N)).

Output

For each test case, print the maximum amount of dollars in total the polices can earn.

Sample

Input	Output
5 3 2 3 1 1 4 1 3 1000 3 2 2 5 1	5 5000 8 15