#1251 · Lên đỉnh Sirius

"Lên đỉnh Sirius" là một cuộc thi kiến thức trên truyền hình nổi tiếng ở đất nước Fasilius. Ở mỗi trận thi, bốn thí sinh sẽ tranh tài ở các vòng thi loại, và chỉ hai thí sinh xuất sắc nhất được phép tham dự vòng thi cuối cùng có tên gọi là vòng Lên đỉnh. Ở vòng Lên đỉnh, điểm của hai thí sinh sẽ được đặt lại về 0, và hệ thống máy tính tối tân sẽ sinh ngẫu nhiên n câu hỏi, mỗi câu hỏi lại có một giá trị điểm nhất định. Hai người chơi sẽ lần lượt chọn mỗi lượt một câu hỏi cho đến khi hết n câu hỏi. Nếu trả lời đúng, người chơi sẽ giành được điểm của câu hỏi đó. Nếu trả lời sai, người chơi không bị trừ điểm.

Giả sử cả hai người chơi đều biết chắc họ sẽ trả lời đúng tất cả các câu hỏi và đều chơi theo một chiến thuật tối ưu nhất, khoảng cách điểm giữa họ sau vòng Lên đỉnh sẽ là bao nhiêu?

• Dòng đầu tiên gồm một số nguyên n, (0 \leq n \leq 10^5) là số câu hỏi được sinh bởi hệ thống máy tính.
• Dòng thứ hai gồm n số nguyên a_1, a_2,..., a_n (0 \leq a_i \leq 10^9), số nguyên a_i là số điểm mà người chơi sẽ nhận được nếu chọn câu hỏi i và trả lời đúng câu hỏi này.

Gồm một dòng duy nhất chứa một số nguyên là khoảng cách điểm giữa hai người chơi sau khi họ đã trả lời hết n câu hỏi một cách chính xác và tối ưu.

Khoảng cách điểm được định nghĩa là hiệu giữa điểm của người có điểm cao hơn và người có điểm thấp hơn.