Cho dãy chữ số ~ s_1, s_2,…,s_n ~; trong đó ~ 0≤ s_i ≤ 9 ~; ~ 1 ≤ n ≤ 10^5 ~.

Hãy cho biết từ chữ số ở vị trí nhứ nhất cần thực hiện ít nhất bao nhiêu bước nhảy để đến được chữ số thứ ~ n ~. Biết rằng:

• Từ vị trí ~ i ~ có thể thực hiện 1 bước để nhảy đến vị trí ~ i-1 ~ hoặc ~ i+1 ~
• Từ vị trí ~ i ~ có thể thực hiện 1 bước để nhảy đến vị trí ~ j ~ ~ (i≠j) ~ nếu ~ s_i = s_j ~

Dữ liệu vào

• Một dòng duy nhất chứa dãy chữ số ~ s_1, s_2,…,s_n ~. Các chữ số được viết liền nhau.

Kết quả

• Một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input 1

01234567890 

Output 1

1