Cho \(1\) mảng có \(n\) số nguyên không âm \(a_1,a_2,...a_n\) và một hoán vị các số từ \(1\) đến \(n\).

Các phần tử sẽ lần lượt bị phá hủy theo thứ tự hoán vị trên. Sau mỗi lần một phần tử bị phá hủy, hãy in ra dãy con liên tiếp có tổng lớn nhất mà không có phần tử nào đã bị phá hủy. Tổng của một đoạn con rỗng là \(0\).

Ràng buộc

• \(1 \le n \le 10^5\)
• \(0 \le a_i \le 10^9\)

Dữ liệu vào

• Dòng đầu tiên là số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1,a_2,...a_n\)
• Dòng thứ ba chứa một hoán vị các số từ \(1\) đến \(n\)

Dữ liệu ra

• \(n\) dòng, dòng thứ \(i\) chứa một số nguyên là tổng lớn nhất của đoạn con liên tiếp không chứa phần tử bị phá hủy sau khi thực hiện hành động xóa thứ \(i\).

Input 1

4
1 3 2 5
3 4 1 2

Output 1

5
4
3
0

Input 2

5
1 2 3 4 5
4 2 3 5 1

Output 2

6
5
5
1
0