Sau khi chia đôi số tiền bán khu rừng zigzag với thằng em tuankiet65, winkhanh đã đi vòng quanh thế giới để tìm kiếm lý tưởng mới cho riêng mình. Tại xứ sở vOz, chàng vô tình gặp và đem lòng yêu mến công chúa Nicolas Hana Isabel. Hai người yêu nhau say đắm và tưởng chừng như sẽ ở bên nhau trọn đời. Đắm chìm trong hạnh phúc lứa đôi, winkhanh dường như đã quên đi mất việc tìm kiếm lý tưởng của cuộc đời mình.
Một ngày nọ, đang tung tăng dạo chơi trong khu vườn Bài Đẹp Trăng nổi tiếng là đẹp nhất thế giới, một cơn cuồng phong bỗng dưng nổi lên, cát bụi bay mù mịt, winkhanh bị đánh ngất đi. Tỉnh dậy, chàng không thấy vị hôn thê của mình đâu nữa mà chỉ còn lại chiếc giày. Đau khổ vô cùng, chàng trở về vương quốc vận động toàn bộ lực lượng quân đội để tìm kiếm tung tích của nàng. Lực lượng siêu khuyển tinh nhuệ nhất của vương quốc được tập hợp với hơn 1696 chú chó berger đã lật tung mọi ngõ ngách lần theo mùi của giày công chúa. Cũng may là công chúa bị bệnh hôi chân rất nặng, thế nên chẳng mấy chốc đã phát hiện ra công chúa bị tên bạo chúa Kong Sanu bắt mất. Chàng quyết định mang theo 1 đạo quân đi cứu công chúa.
Trải qua 80 kiếp nạn, đạo quân chàng mang theo chỉ còn lại mình chàng và chàng phải vượt qua cạm bẫy cuối cùng trước khi cứu được công chúa. Với cặp mắt tinh tường của mình, winkhanh phát hiện ra cạm bẫy này vốn là một con đường chia thành N ô phủ đầy khí gas độc, chưa kể, cứ sau mỗi T[i] giây, ô thứ i sẽ phát nổ. Sau mỗi giây, cậu ta bắt buộc phải di chuyển sang 1 ô kề với ô đang đứng, không thể đứng im tại một ô vì như vậy hệ thống báo động sẽ kêu lên và công sức của cả đoàn quân sẽ đổ sông đổ biển.
Hiện tại winkhanh đang đứng ở ô S và công chúa bị nhốt ở ô D, quá kiệt sức sau 80 kiếp nạn trước, winkhanh không còn khả năng để suy nghĩ nữa, cậu đã gọi cho đội quân HSG tin THCS để nhờ trợ giúp, hãy mau mau giúp winkhanh cứu lấy tình yêu của đời mình.
Yêu cầu: Cho biết con đường dài N ô, và cho biết các giá trị T[i] thể hiện: sau T[i] giây thì ô thứ i sẽ phát nổ. Ô thứ i sẽ không bao giờ phát nổ nếu T[i] = -1. Hiện nay winkhanh đang xuất phát ở ô (S), mỗi giây đều phải di chuyển sang trái hoặc sang phải (không được ra khỏi con đường). Hãy tính thời gian ít nhất mà winkhanh có thể đến được ô (D).
Input:
Output: Một dòng duy nhất chứa thời gian nhỏ nhất để winkhanh có thể cứu được công chúa hoặc -1 nếu không có cách nào có thể đến được vị trí của công chúa.
Lưu ý: ở thời điểm 0, các ô không phát nổ.