DPAIR - Counting d-pairs

You're given a sequence A of N non-negative integers. Answer Q queries, where each query consists of two integers: a, b. The answer is number of pairs of integers i and j that satisfy these three conditions:

  1. 1 <= i <= j <= N
  2. a <= j-i+1 <= b
  3. all elements of A with indices from range [i, j] are mutually distinct. (indexing starts with 1)

Constraints:
1 <= N <= 8*10^5
1 <= Q <= 2*10^5
0 <= A[k] <= 10^6, for every integer k between 1 and N, inclusive
1 <= a <= b <= N

Input

First line of input contains integer N. Second line contains N integers representing sequence A. Third line is integer Q, number of queries. Next Q lines have 2 integers, a and b.

Output

In the i-th line output the answer for i-th query.

Example

Input:
5
1 2 3 4 5
1
1 1

Output:
5

NOTE: IO is huge


Added by:Buda IM
Date:2011-09-16
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:own problem, thanks to lpp

hide comments
2013-03-11 23:20:06 tainic
Isn't the time limit too low? I'm pretty sure my algorithm is optimal, but I still get TLE in Java even if using IO optimizations... In fact I can see that nobody was able to solve this in Java...

EDIT (by BudaIM): Yes indeed, TL is too strict for JAVA. It was between that or letting non-optimal solutions to pass.

Last edit: 2013-03-19 15:31:24
2012-08-20 19:00:20 lxyxynt
O(N) algorithm still got TLE.. I get AC with I/O optimize at last. I really want to know how to get AC in 1s

Last edit: 2012-08-20 19:03:56
2012-02-26 13:00:43 Ravi Kiran
Nice problem! :-)

Last edit: 2011-09-19 17:37:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.