VISION - Vision Field

no tags 

There are N buildings stand along the horizon line. Each building are represented as a vertical segment with two end points at (i, 0) and (i, Ai). There are M queries in total. For each query, we wonder know how many buildings you can see if you stand at (0, h).

... N, M ≤ 106, both Ai and h is positive integer and ≤ 109.

Input

N
A1 A2 ... An
M
(here following the M queries.)

Output

For each query, simply print how many buildings you can see.

Example

Input:
5
2 3 3 3 4
3
3
2
4

Output:
3
2
5

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-06-09 00:06:52

Well, I must admit that C++ standard library is MUCH FASTER, than C :-O

(Tjandra Satria Gunawan)(曾毅昆): 2015-06-08 23:47:57

[!] Test case is really strong, I can't "cheat" this problem with my usual optimization trick :-O

Bhavik: 2014-02-23 19:48:42

@xiaodao:
can you kindly look at my id:11140426 giving WA..and tell if i am interpreting the question correctly..

THANK YOU

Last edit: 2014-02-27 09:59:08

Added by:xiaodao
Date:2012-12-20
Time limit:0.305s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem