Phá huỷ mảng

Cho một mảng $a_1,a_2,\dots ,a_n$ gồm $n$ số nguyên không âm và một hoán vị $p_1,p_2,\dots ,p_n$ của các số từ $1$ đến $n$ chỉ định thứ tự phá huỷ các phần tử.

Tại bước thứ $i$ (với $i=1,2,\dots ,n$), phần tử ở vị trí $p_i$ bị phá huỷ. Sau mỗi bước, bạn cần tìm đoạn con liên tiếp của mảng sao cho đoạn đó không chứa phần tử nào đã bị phá huỷ và tổng các phần tử trong đoạn là lớn nhất có thể. Tổng của đoạn rỗng được quy ước bằng $0$.

In ra giá trị tổng lớn nhất sau mỗi bước phá huỷ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — các phần tử của mảng.
• Dòng thứ ba chứa hoán vị $p_1,p_2,\dots ,p_n$ — thứ tự phá huỷ.

Dữ liệu ra

In ra $n$ dòng. Dòng thứ $i$ chứa tổng lớn nhất của một đoạn con liên tiếp không bị phá huỷ, sau khi đã thực hiện $i$ thao tác phá huỷ đầu tiên.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le a_i\le {10}^9$
• $p$ là hoán vị của $1,2,\dots ,n$.

Ví dụ