Bitlər təhlükəlidir

Siz düşünürsünüz ki, yuxudan qaçmaq asandır? Bu, bitlər haqqında olan yuxu deyil. Yəqin ki, dünən çoxlu nəzəriyyə oxumusunuz, amma bu artıq əhəmiyyətli deyil. Tək istədiyiniz şey oyanmaqdır. Yəqin ki, ən yaxşı xüsusi sıranı səhv hesablamısınız... ya da onlar sizi aldatdılar. Uzun bitlər sırası hələ də qapalı gözlərinizin önündədir.

Sonra anladınız ki, bu sıranın ən sol bitini 0-dan 1-ə və ya 1-dən 0-a dəyişmək imkanınız var. Bu dəqiq dörd saniyə çəkir, amma bunu edə bilərsiniz!

Sonra aşkar etdiniz ki, sıranı bir mövqeyə sola və ya bir mövqeyə sağa dövrü şəkildə sürüşdürə bilərsiniz. Bu qəribə yuxuda istənilən bu hərəkət yeddi saniyə çəkir.

Bir şey sizə deyir ki, məhz 1-bitlər sizi yuxuda saxlayır. Əgər bu birdən doğru olsa, siz bütün sıranı sıfırlara çevirməyə qərar verdiniz. Bunun üçün lazım olan hər şeyə sahibsiniz.

Amma bunu optimal şəkildə etmək üçün nə qədər vaxt lazımdır?

Giriş verilənləri

Yeganə sıra S (2 ≤ |S| ≤ 2∙10^5), sıfırlardan və birlərdən ibarətdir.

Çıxış verilənləri

Sıranı S tamamilə sıfırlardan ibarət sıraya çevirmək üçün lazım olan ən az vaxtı, saniyələrlə çıxarın.

Nümunələr

Qeyd

Birinci testdə optimal strategiya belə olacaq: sol biti dəyişirik: 01001, sıranı dövrü şəkildə sola sürüşdürürük: 10010, sol biti dəyişirik: 00010, sıranı dövrü şəkildə sağa sürüşdürürük: 00001, sıranı dövrü şəkildə sağa sürüşdürürük (yenidən): 10000, sol biti dəyişirik: 00000. Üç dəyişiklik və üç dövrü sürüşdürmə tam olaraq 33 saniyə çəkəcək.