Food_Distribution2

Sau khi phân phát lần thứ nhất, nhà vua thấy có sự không công bằng bởi các tỉnh bởi có tỉnh thì giàu, tỉnh thì nghèo nên không thể phân phát cùng một số lượng đồ ăn được. Nhà vua quyết định giao cho bên tể tướng thống kê số kilogram đồ ăn đã có của các tỉnh và từ đó có kế hoạch phân phát hợp lý. Sau khi thống kê xong, tể tướng đi vào bàn nhậu với các quan đại thần. Có người thách tể tướng là ông có thể phân phát sao cho:

• Nếu có một tỉnh được phân phát a kilogram đồ ăn thì chắc chắn một trong hai tỉnh kề với nó theo thứ tự mảng cũng sẽ được phân phát a kilogram đồ ăn sao cho sau khi phân phát, tất cả các tỉnh đều có số kilogram đồ ăn là số nguyên chẵn không âm.
• Số kilogram đồ ăn được phân phát là ít nhất và chỉ ra số đó.

Hãy giúp tể tướng giải quyết vấn đề này. Cho mảng food chứa thông tin số kilogram đồ ăn của các tỉnh, hãy cho biết số kilogram đồ ăn ít nhất có thể được phân phát để thỏa điều kiện nếu phân phát được, nếu không thể phân phát được, hãy trả về -1.

Ví dụ:

• Với food = [1, 2, 3, 6] thì ta có thể phân phát :
  Cho tỉnh thứ nhất thì tỉnh thứ hai cũng được nhận nên food sẽ là [2, 3, 3, 6]
  Cho tỉnh thứ hai và chọn tỉnh được nhận là tỉnh thứ ba nên food sẽ là [2, 4, 4, 6]
  Ta đã phân phát 4 kilogram đồ ăn (ít nhất có thể) nên đáp án sẽ là 4.

• Với food = [1,2,3,7] thì không thể phân phát được nên đáp án sẽ là -1.

Đầu vào / Đầu ra:

• [Giới hạn thời gian] 0.1 giây với C++, 0.6 giây với Java và C#, 0.8 giây với Js, Go và Python
• [Đầu vào] Array of Integer food
  1 <= food.size() <= 10^5
0 <= food[i] <= 1000

• [Đầu ra] integer
  Đáp án của hàm distributeFood2