Trò chơi Trung vị

Trong một buổi thảo luận về vật lý lượng tử, FullHouse Dev đã được đưa ra một bài toán thú vị liên quan đến trung vị của dãy số. Mặc dù không trực tiếp liên quan đến vật lý, nhưng bài toán này đã kích thích trí tò mò của nhóm và họ quyết định giải quyết nó.

Bài toán

Bạn được cho một mảng \(A\) gồm \(N\) số nguyên. Bạn thực hiện thao tác sau \(N\) lần: Với mỗi mảng con liên tiếp có kích thước lẻ lớn hơn \(1\), bạn tìm trung vị của mỗi mảng con (Giả sử các trung vị thu được trong một lượt là \(M_1, M_2, ...\)). Trong mỗi lượt, bạn loại bỏ phần tử đầu tiên có giá trị \(min(M_1, M_2, ...)\) khỏi mảng ban đầu. Sau khi loại bỏ phần tử, kích thước mảng giảm đi 1 và không có khoảng trống nào được để lại.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng bộ test (\(1 \leq T \leq 10\)).
• Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\) là số lượng phần tử trong mảng ban đầu (\(1 \leq N \leq 10^5\)).
• Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn mảng \(A\) (\(1 \leq A_i \leq 10^9\) với mọi \(i\) hợp lệ).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra một số nguyên duy nhất biểu diễn tổng các số còn lại trong mảng sau khi thực hiện các thao tác.

VÍ DỤ:

INPUT

2
4
2 5 3 2
4
1 1 1 1

OUTPUT

7
2

Giải thích:

• Đối với bộ test đầu tiên: Ban đầu, mảng là \([2, 5, 3, 2]\). Các trung vị thu được là \(2\) và \(3\) cho các mảng con \([2, 5, 3]\) và \([5, 3, 2]\) tương ứng. Do đó, chúng ta loại bỏ \(2\) khỏi mảng ban đầu. Mảng bây giờ trở thành \([5, 3, 2]\). Trung vị của toàn bộ mảng là \(3\). Do đó, chúng ta loại bỏ lần xuất hiện đầu tiên của \(3\) khỏi mảng. Vậy chúng ta còn lại với mảng \([5, 2]\).

• Đối với bộ test thứ hai, rõ ràng trung vị nhỏ nhất sẽ luôn là \(1\) mỗi lần. Do đó, cuối cùng chúng ta sẽ còn lại với mảng \([1, 1]\).