Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng N ngày lần lượt là A₁, A₂, …, A_N. Mỗi ngày Bình chỉ thực hiện đúng một trong ba hoạt động: (1) mua một cổ phiếu VNI; (2) bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu; (3) không thực hiện giao dịch nào.

Yêu cầu: Với mỗi ngày bắt đầu T cho trước, hãy xác định cách giao dịch để lợi nhuận thu được là lớn nhất nếu Bình chỉ được tham gia mua bán kể từ ngày thứ T trở đi.

Input:

Dòng đầu tiên là số nguyên dương N (N ≤ 10⁵) - số ngày biết giá cổ phiếu.
Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N (A_i ≤ 10⁹).
Dòng thứ ba là số nguyên dương Q (Q ≤ 10⁵) - số truy vấn.
Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương T (T ≤ N) - ngày đầu tiên Bình bắt đầu tham gia mua bán.

Output: In ra Q dòng, mỗi dòng là một số nguyên dương duy nhất- lợi nhuận lớn nhất Bình có thể thu được cho truy vấn tương ứng.

Ràng buộc chấm điểm:
50% test: N ≤ 1000; Q = 1.
30% test: N ≤ 10⁵; Q = 1.
20% test còn lại: không có ràng buộc thêm.

Ví dụ

Input

4
1 2 5 4
2
1
3

Output

7
0

Giải thích: Nếu bắt đầu từ ngày 1, mua ở ngày 1 (giá 1) và ngày 2 (giá 2), bán cả hai ở ngày 3 (giá 5) ⇒ lợi nhuận = -1 -2 + 2×5 = 7. Nếu bắt đầu từ ngày 3 thì giá giảm nên lợi nhuận lớn nhất là 0.