Dino viết một dãy số nguyên có ~n~ phần tử lên trên bảng, lần lượt xếp thành một hàng. Mỗi lần, Dino dùng phấn gạch bỏ đi một số trên bảng theo thứ tự tùy ý của Dino. Sau ~n~ lượt, Dino đã gạch hết tất cả các số trong dãy.

Trước mỗi lần gạch, Dino muốn bạn tìm dãy con liên tiếp có tổng lớn nhất mà không chứa những số đã được gạch. Hãy in ra tổng của dãy con liên tiếp đó.

Dữ liệu vào:

• Dòng đầu tiên chứa ~n~ ~(1≤n≤10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên không vượt quá ~10^9~: dãy số ban đầu được Dino viết lên bảng.
• Dòng thứ ba chứa ~n~ số nguyên: ~p_1,p_2,…,p_n~, với ~p_i~ là vị trí của phần tử được xóa trong lượt thứ ~i~. ~(1≤p_i≤n, ∀ i,j:p_i≠p_j)~.

Kết quả:

• Dòng thứ ~i~, in ra kết quả tìm được trước khi Dino xóa số thứ ~i~ trong dãy.

Giới hạn:

• 30% số điểm: ~n≤5000~.
• 70% số điểm còn lại không ràng buộc gì thêm

Ví dụ:

Input:

5
6 1 2 3 2
2 5 1 4 3 

Output:

14
7
6
5
2 

Giải thích:

• Bước 1: ~[6, 1, 2, 3, 2]~ => chọn đoạn ~[1,5]~ => Tổng ~14~
• Bước 2: ~[6, x, 2, 3, 2]~ => chọn đoạn ~[3,5]~ => Tổng ~7~
• Bước 3: ~[6, x, 2, 3, x]~ => chọn đoạn ~[1,1]~ => Tổng ~6~
• Bước 4: ~[x, x, 2, 3, x]~ => chọn đoạn ~[3,4]~ => Tổng ~5~
• Bước 5: ~[x, x, 2, x, x]~ => chọn đoạn ~[3,3]~ => Tổng ~2~