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 ≤ 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 ≤ 10^9; 1 ≤ i ≤ N\));
• Dòng thứ ba gồm một số nguyên dương \( Q \) là số lượng truy vấn ( \( Q ≤ 10^5 \) );
• \(Q\) dòng sau, mỗi dòng gồm một số nguyên dương \( T \) ( \( T ≤ 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

• \( 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.

Scoring

• Có 50% số test ứng với 50% số điểm của bài thoả mãn: \( N ≤ 1000; Q = 1\);
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: \( N ≤ 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.

Example

4
1 2 5 4
2
1
3

7
0