사탕

탁자 위에 N개의 사탕이 일렬로 놓여 있다. 각 사탕에는 맛있다는 정도를 나타내는 값이 있다. 왼쪽에서 i번째 사탕의 맛은 $A_i$이다 ($1 \le i \le N$).

JOI-chan은 이 N개의 사탕 중 일부를 먹기로 했다. JOI-chan은 자신이 먹을 사탕들의 맛의 합을 최대로 하고 싶다.

그런데 JOI-chan은 사탕을 그냥 탐욕스럽게 고르는 것은 재미없다고 생각해서, 연속한 두 사탕을 동시에 고를 수 없다는 규칙을 만들었다.

JOI-chan은 사탕을 몇 개 먹을지 정하지 않았으므로, 각 $j$ ($1 \le j \le \lceil N/2 \rceil$)에 대해 사탕을 j개 먹을 때의 맛의 합의 최댓값을 알고 싶어 한다. 여기서 $\lceil x \rceil$는 x보다 작지 않은 가장 작은 정수이다.

사탕의 개수와 각 사탕의 맛이 주어졌을 때, 각 $j$ ($1 \le j \le \lceil N/2 \rceil$)에 대해 사탕을 j개 먹을 때의 맛의 합의 최댓값을 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에는 정수 N이 주어진다. 이는 탁자 위에 N개의 사탕이 있다는 뜻이다.
• 다음 N개의 줄 중 i번째 줄 ($1 \le i \le N$)에는 정수 $A_i$가 주어진다. 이는 왼쪽에서 i번째 사탕의 맛이 $A_i$라는 뜻이다.

표준 출력에 $\lceil N/2 \rceil$개의 줄을 출력한다. 출력의 j번째 줄 ($1 \le j \le \lceil N/2 \rceil$)에는 사탕을 j개 먹을 때의 맛의 합의 최댓값을 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).