THỰC HÀNH

Cho dãy số nguyên A = (a₀, a₁, … , aₙ₋₁). Bạn được phép xóa đi một phần tử có giá trị nhỏ nhất hoặc xóa đi một phần tử có giá trị lớn nhất trong dãy.

Yêu cầu: Tìm cách dùng ít nhất các phép xóa theo luật trên để thu được một dãy mới có tổng các phần tử trong dãy bằng 0. (Dãy rỗng cũng được coi là dãy có tổng các phần tử bằng 0).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n ≤ 10⁵;
• Dòng thứ hai chứa n số nguyên a₀, a₁, … , aₙ₋₁ cách nhau bởi dấu cách (∀i: |aᵢ| ≤ 10⁹).

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là số phép xóa cần thực hiện.

Ví dụ:

Dữ liệu vào:

-4 -5 1 2 -3 10

Dữ liệu ra:

3

Dữ liệu vào:

8
-3 -3 -3 0 0 0 4 4

Dữ liệu ra:

5

Dữ liệu vào:

9
1 2 3 4 5 6 7 8 9

Dữ liệu ra:

9