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_1, A_2, ..., A_N~. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

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 bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ ~T~ cho trước?

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ (~N \le 10^5~) là số ngày biết giá cổ phiếu;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ tương ứng là giá của một cổ phiếu VNI trong từng ngày (~A_i \le 10^9~; ~1 \le i \le N~);
• Dòng thứ ba gồm một số nguyên dương ~Q~ là số lượng truy vấn (~Q \le 10^5~);
• ~Q~ dòng sau, mỗi dòng gồm một số nguyên dương ~T~ (~T \le N~) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Output

Gồm ~Q~ dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Sample Input 1

4
1 2 5 4
2
1
3

Sample Output 1

7
0

Bình bắt đầu tham gia mua bán VNI vào ngày 1:

• Ngày 1: mua 1 VNI với giá là 1.
• Ngày 2: mua 1 VNI với giá là 2.
• Ngày 3: bán 2 VNI với giá là 5.
• Ngày 4: không mua hay bán VNI vào ngày này.

~\Rightarrow~ Lợi nhuận thu được là: ~-1 - 2 + 2 \times 5 = 7~.

Bình bắt đầu tham gia mua bán VNI vào ngày 3:

• Bình không mua bán VNI vào ngày 3 và ngày 4.

~\Rightarrow~ Lợi nhuận thu được là: ~0~.

Subtasks

• Có 50% số test ứng với 50% số điểm của bài thoả mãn: ~N \le 1000~; ~Q = 1~;
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: ~N \le 10^5~; ~Q = 1~;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.