Có một khu rừng có độ dài ~n~ ô đất và cứ mỗi một ô đất thứ ~i~ lại mọc lên 1 cái cây có chiều cao ~a_i~. Có những con sóc bay chỉ thích sống trên đỉnh các ngọn cây và chúng rất thích bay lượn.

Những chú sóc chỉ thích bay lượn và đáp trên các ngọn cây mà:

• Cây đó phải thấp hơn hoặc bằng cây của chú sóc đang đứng.
• Sóc không thể bay xuyên qua các ngọn cây cao hơn cây đang đứng.

Có ~q~ câu hỏi rằng liệu chú sóc ở ngọn cây ~x_i~ thì có thể bay tới tối đa bao nhiêu cây.

Input

• Dòng đầu tiên có số nguyên ~N~ ~(1 \leq N \leq 5 \times 10^5)~ đại diện cho chiều dài khu rừng.
• Dòng tiếp theo có ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq N)~ đại diện cho chiều cao của cây thứ ~i~
• Dòng tiếp theo có một số nguyên ~Q~ ~(1 \leq Q \leq 5 \times 10^5)~ đại diện cho số truy vấn.
• ~Q~ dòng tiếp theo với mỗi dòng có một số nguyên ~x_i~ ~(1 \leq x_i \leq N)~ đại diện cho truy vấn của chú sóc ở vị trí thứ ~x_i~.

Output

• ~Q~ dòng tương ứng với đáp án của mỗi truy vấn là số lượng cây mà chú sóc có thể bay tới

Sample Input 1

6
8 2 3 1 3 4
2
3
4

Sample Output 1

4
1

Sample Input 2

5
3 2 3 1 5
2
1
2

Sample Output 2

4
1