San nền

Bài 1/3
Một tuyến đường có chiều dài N và được chia thành N đoạn đánh số từ 1 đến N. Để làm được việc này thì đầu tiên phản san nền cho vùng đất mà tuyến đường sẽ đi qua. Ban đầu, nền đường tại đoạn thứ i có chiều cao là Hi và người ta muốn sau khi san nền, tất cả các đoạn nền đường đều có cùng độ cao là K. Để làm được việc đó thì tại những đoạn đường có độ cao là Hi > K người ta cần đào đi một lượng đất là Hi - K và tại nhưng đoạn đường có độ cao là Hi < K người ta cần đổ thêm một lượng đất là k - Hi. Trong quá trình san nền tuyến đường, cho phép sử dụng đất ở những đoạn bị để đắp vào đoạn nào đó của tuyến đường nếu cần thiết. Gọi S là lượng đất bắt buộc phải vận chuyển từ bên ngoài tuyến đường vào để đắp hoặc chuyển từ tuyến đường ra bên ngoài để toàn bộ tuyến đường có độ cao là K.
Yêu cầu: Tìm số nguyên dương K nhỏ nhất sao cho giá trị số S là nhỏ nhất.
Dữ liệu vào: Đọc từ file văn bản BL1.INP, có cấu trúc như sau:
   - Dòng đầu tiên ghi số nguyên dương N là chiều dài của đoạn đường.
   - Dòng thứ hai ghi N số nguyên dương H1, H2, ..., Hn. Hai số liên tiếp cách nhau bở một khoảng trống.
Dữ liệu ra: Ghi ra file BL1.OUT duy nhất số nguyên K tìm được.
Ví dụ:
   BL1.INP          BL1.OUT                 BL1.INP           BL1.OUT                    BL1.INP       BL1.OUT
   7                      3                               8                        2                                  4                   2
   1 3 4 2 1 2 5                                     1 1 1 1 5 1 1 1                                       1 3 1 3
Giới hạn: 1<=N<=15x10^3; Hi<=10^5.

                                                                     Loi giai tham khao