#include <iostream> // Dành cho cin, cout [4]
#include <vector> // Dành cho std::vector, mặc dù ở đây dùng mảng tĩnh. [5]
#include <queue> // Dành cho std::priority_queue [6]
#include <algorithm> // Dành cho std::max hoặc các hàm khác nếu cần, ceil(N/2) có thể dùng (N+1)/2 cho số nguyên dương [7]
// Định nghĩa kích thước tối đa cho N. Vì có thể tạo thêm virtual candies,
// kích thước mảng cần lớn hơn N. Tối đa N + ceil(N/2) phần tử.
// N_MAX = 200,000. => 200,000 + 100,000 = 300,000.
// Dùng 2 * N_MAX_REAL_CANDIES để an toàn.
const int N_MAX_REAL_CANDIES = 200005; // N + 5 for safety buffer
const int MAX_TOTAL_CANDIES = N_MAX_REAL_CANDIES * 2; // Đủ cho real và virtual candies
long long A[MAX_TOTAL_CANDIES]; // Mảng lưu giá trị ngon miệng của kẹo (thực và ảo) [1]
int L[MAX_TOTAL_CANDIES], R[MAX_TOTAL_CANDIES]; // Mảng danh sách liên kết đôi [CPH.pdf]
bool deleted[MAX_TOTAL_CANDIES]; // Mảng đánh dấu kẹo đã bị xóa (không hợp lệ)
// Cặp (giá_trị, chỉ_số) để lưu trong priority_queue.
// std::priority_queue mặc định là max-heap (lấy phần tử lớn nhất).
using Candy = std::pair<long long, int>;
// Mảng lưu trữ các câu trả lời cho mỗi j (số lượng kẹo được ăn)
long long answers[N_MAX_REAL_CANDIES / 2 + 5];
int main() {
// Tối ưu hóa I/O để đọc/ghi nhanh hơn [4, 8]
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int N; // Số lượng viên kẹo ban đầu [7]
std::cin >> N;
// Hàng đợi ưu tiên để lưu trữ các viên kẹo tiềm năng (giá trị, chỉ số)
std::priority_queue<Candy> pq;
// Khởi tạo các viên kẹo thực tế và danh sách liên kết đôi
for (int i = 0; i < N; ++i) {
std::cin >> A[i]; // Đọc giá trị ngon miệng của kẹo thứ i [1]
L[i] = i - 1; // Chỉ số kẹo bên trái
R[i] = i + 1; // Chỉ số kẹo bên phải
deleted[i] = false; // Ban đầu chưa có kẹo nào bị xóa
pq.push({A[i], i}); // Thêm kẹo vào hàng đợi ưu tiên
}
R[N - 1] = -1; // Viên kẹo cuối cùng không có hàng xóm bên phải
long long current_total_sum = 0; // Tổng giá trị ngon miệng hiện tại
int candies_eaten_count = 0; // Số lượng kẹo đã ăn
// Bộ đếm ID cho các viên kẹo ảo, bắt đầu từ N
// Các ID này sẽ không trùng với ID của các viên kẹo thực (0 đến N-1)
int virtual_candy_id_counter = N;
// Số lượng kẹo tối đa có thể ăn là ceil(N/2) [7]
// Sử dụng phép chia số nguyên (N + 1) / 2 để tính ceil(N/2) cho số nguyên dương
int max_candies_to_eat = (N + 1) / 2;
// Vòng lặp chính: chọn kẹo cho đến khi đạt số lượng tối đa hoặc PQ trống
while (candies_eaten_count < max_candies_to_eat && !pq.empty()) {
Candy top_candy = pq.top(); // Lấy viên kẹo có giá trị cao nhất
pq.pop(); // Xóa khỏi PQ
long long val = top_candy.first; // Giá trị của viên kẹo
int idx = top_candy.second; // Chỉ số của viên kẹo
if (deleted[idx]) { // Nếu viên kẹo này đã bị xử lý (do bị chọn hoặc bị loại bỏ bởi hàng xóm)
continue; // Bỏ qua và lấy viên kẹo tiếp theo
}
// Chọn viên kẹo này
current_total_sum += val;
candies_eaten_count++;
answers[candies_eaten_count] = current_total_sum; // Lưu kết quả cho j viên kẹo
// Đánh dấu viên kẹo hiện tại là đã bị xóa (vì đã chọn)
deleted[idx] = true;
// Lấy hàng xóm của viên kẹo vừa chọn
int left_neighbor = L[idx];
int right_neighbor = R[idx];
// Đánh dấu các viên kẹo lân cận là đã bị xóa (vì không thể chọn chúng)
if (left_neighbor != -1) {
deleted[left_neighbor] = true;
}
if (right_neighbor != -1) {
deleted[right_neighbor] = true;
}
// Tạo một viên kẹo ảo mới. Giá trị của nó là tổng của hai hàng xóm
// trừ đi giá trị của viên kẹo hiện tại đã chọn.
// Đây là "sự hối tiếc" nếu chúng ta đã chọn hàng xóm thay vì kẹo hiện tại.
long long new_val = 0;
if (left_neighbor != -1) {
new_val += A[left_neighbor];
}
if (right_neighbor != -1) {
new_val += A[right_neighbor];
}
new_val -= A[idx]; // Trừ đi giá trị của kẹo đã chọn để tính net change
int new_id = virtual_candy_id_counter++; // Gán ID mới cho kẹo ảo
A[new_id] = new_val; // Lưu giá trị của kẹo ảo
// Cập nhật con trỏ của danh sách liên kết đôi cho viên kẹo ảo mới
// Viên kẹo ảo sẽ nối các hàng xóm cũ của L[idx] và R[idx]
L[new_id] = (left_neighbor != -1 ? L[left_neighbor] : -1);
R[new_id] = (right_neighbor != -1 ? R[right_neighbor] : -1);
// Cập nhật lại con trỏ của các hàng xóm xa hơn để chúng trỏ đến viên kẹo ảo mới
if (L[new_id] != -1) { // Nếu có hàng xóm bên trái xa hơn
R[L[new_id]] = new_id;
}
if (R[new_id] != -1) { // Nếu có hàng xóm bên phải xa hơn
L[R[new_id]] = new_id;
}
// Thêm viên kẹo ảo mới vào hàng đợi ưu tiên
pq.push({new_val, new_id});
}
// In ra kết quả cho mỗi j [1]
for (int j = 1; j <= max_candies_to_eat; ++j) {
std::cout << answers[j] << "\n";
}
return 0;
}
