Найбільше кульок
Limits: 2 sec., 256 MiB
У Зеника є n кульок, розміщених в ряд. i-та (зліва направо) кулька важить ai грам, початково усі кульки розфарбовано у чорний колір.
Марічка послідовно (у заданому порядку) розфарбовує кульки у білий колір. Після кожного розфарбування Зенику цікаво, яку найбільшу сумарну вагу він може отримати, вибравши набір послідовних білих кульок?
Ваше завдання — допомогти йому знайти відповіді.
Input
У першому рядку задано одне ціле число n — кількість кульок.
У другому рядку задано n цілих чисел ai, розділених пробілами — ваги кульок (зліва направо).
У третьому рядку задано перестановку p цілих чисел від 1 до n — номера кульок, які Марічка фарбує в білий колір на кожному наступному кроці.
Output
У єдиному рядку виведіть n цілих чисел розділених пробілами — відповіді на задачу після розфарбування чергової кульки.
Constraints
1≤n≤2⋅105.
0≤ai≤109,
1≤pi≤n, усі pi — різні.
Samples
Input (stdin) | Output (stdout) |
---|---|
7 10 1 4 4 2 7 4 4 6 3 5 1 2 7 | 4 7 8 17 17 28 32 |
Notes
4-а кулька стає білою, її вага — 4. Відповідь — 4, адже всі інші кульки чорні.
6-а кулька стає білою, її вага — 7. Оскільки кулька 4 та 6 не є сусідніми, не можна вибрати їх обох, отже відповідь — 7.
3-а кулька стає білою, її вага — 4. Найкраще вибрати 3-тю та 4-ту (сусідні) кульки із сумарною вагою 8.
5-а кулька стає білою, її вага — 2. Найкраще вибрати кульки 3, 4, 5 та 6 з сумарною вагою 17.
1-а кулька стає білою, її вага — 10. Найкраще вибрати кульки 3, 4, 5 та 6 з сумарною вагою 17.
2-а кулька стає білою, її вага — 1. Найкраще вибрати кульки 1, 2, 3, 4, 5 та 6 з сумарною вагою 28.
7-а кулька стає білою, її вага — 4. Усі кульки білі, тому можна вибрати усі з сумарною вагою 32.