#1320. STOVE

Bé Đạo hôm nay đến thực tập tại một nhà hàng và hiện tại đang đứng trước một cái bếp ga có núm.

Mỗi núm ga có thể xoay theo cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ với số bước tuỳ ý. Giả sử xoay theo chiều kim đồng hồ bước với núm trên thì độ nóng của núm mới là . Với mỗi thao tác bé Đạo có thể vặn một chuỗi các núm liên tiếp theo cùng một chiều và cùng một số lượng bước. Dù xoay bao nhiêu bước trong một lần. thì vẫn tính là một thao tác. Bé Đạo muốn tìm số bước ít nhất sao cho độ nóng của cả nút là lớn nhất. Các bạn hãy giúp bạn ấy nhé!

Dữ liệu vào:

• Dòng đầu tiên bao gồm một số là số lượng núm;
• dòng sau, dòng thứ là số biểu thị độ nóng ban đầu của núm thứ .

Dữ liệu ra:

• Gồm một số duy nhất là số thao tác ít nhất cần thực hiện.

Ví dụ:

Dữ liệu vào:

7
3528482
9763459
6523528
7345526
1537354
1834632
7473823

Dữ liệu ra:

5

Dữ liệu vào:

7
5383638
6283637
6484936
1927493
1637478
5373838
6483826

Dữ liệu ra:

4

Giới hạn:

• Trong tất cả các test, các chữ số trên các núm là các số từ 1 đến 9 và luôn có chữ số.
• Subtask số điểm có ;
• Subtask số điểm còn lại có .