+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، سر و صدای زیادی به راه افتاد؛ به طوری که خبرنگاران پشت در صف کشیده و مشغول تهیه گزارش از این خبر مهم شدند. تیم کوئرا که نتوانستند در آن سر و صدا کار کنند تصمیم گرفتند که به کافه گراف بروند و آنجا کارشان را ادامه دهند. کارگرانی که در کوئرا مشغول تغییر دکوراسیون شرکت بودند هم نتوانستند در این سر و صدا کار کنند و تصمیم گرفتند که آن‌ها هم همراه تیم کوئرا به کافه گراف بروند و کارشان را آنجا ادامه دهند! اکنون همه در شرکت گیر کرده‌اند و اگر در را باز کنند خبرنگاران به داخل خواهند ریخت. از این رو آنها از پنجره به پشت بام رفتند و می‌خواهند از روی پشت‌بام‌ها بپرند تا سیل عظیم خبرنگاران را رد کنند. از پشت بام شرکت تا جایی که دیگر از خبرنگاران خبری نباشد تعدادی پشت‌بام در یک خط وجود دارد.(پشت‌بام‌ها را از ۰ تا $n$ به ترتیب شماره‌گذاری می‌کنیم. پشت‌بام شرکت شماره‌ی ۰ است) زمانی که آنها به پشت‌بام $n$ برسند دیگر از خبرنگاران خبری نخواهد بود. خوشبختانه چون آن‌ها خیلی بافرهنگ هستند ابتدا به تمامی صاحب‌های ‌پشت‌بام‌ها زنگ زدند و از آن‌ها اجازه گرفتند. آن‌ها هم در این صورت اجازه‌ی عبور دادند که پول تعمیر پشت‌بامشان توسط شرکت پرداخته شود. پول تعمیر هم به این صورت پرداخته می‌شود که صاحب پشت‌بام $i$، برای پشت‌بامش یک قیمت $c_i$ اعلام کرده است و اگر بچه‌ها از پشت بام $j$ روی آن بپرند باید به اندازه‌ی $|j-i| \times c_i $ پرداخت کنند.( هر چی دورتر باشند فشار بیشتری به پشت‌بام مقصد وارد می‌شود.) حالا بچه‌ها می‌خواهند با کمترین هزینه به پشت‌بام $n$ برسند. این هزینه را به بچه‌ها بگویید. # ورودی در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد پشت‌بام‌ها می‌باشد. سپس در خط بعد $n$ عدد آمده‌ است که عدد $i$، نمایانگر $c_i$ می‌باشد. $$ 1 \le n \le 1 \ 000 \ 000 $$ $$ 1 \le c_i \le 1 \ 000 \ 000 \ 000 $$ # خروجی در یک سطر خروجی کمینه‌ی هزینه‌ی جابجایی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 5 4 5 ``` ## خروجی نمونه ۱ ``` 13 ``` توضیح: در این مثال حالت بهینه این است که ابتدا از بام ۰ به بام ۲ بروند که هزینه‌ی این کار $2 \times 4$ می‌باشد. سپس از بام ۲ به بام ۳ بروند که هزینه‌ی این کار $ 1 \times 5$ می‌باشد که در مجموع می‌شود ۱۳. ## ورودی نمونه ۲ ``` 1 5 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۳ ``` 4 ``` ## ورودی نمونه ۴ ``` 5 3 2 3 2 4 ``` ## خروجی نمونه ۴ ``` 12 ```