+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میدان اصلی شهر کدکاپ بسیار بزرگ است. دور این میدان $n$ چراغ روشنایی قرار دارد. این چراغ‌ها را با اعداد ۱ تا $n$ به ترتیب ساعت‌گرد شماره‌گذاری کرده‌اند.  می‌دانیم اگر یک چراغ روشن شود، محوطه زیر آن و دو چراغ مجاورش روشن می‌شود. به صورت رسمی‌تر اگر چراغ شماره‌ی $i$ را روشن کنیم، ($1 \leq i \leq n$) محوطه‌ی زیر چراغ $i$، $i - 1$ و $i + 1$ روشن می‌شود. (اگر $i + 1$ از $n$ بیشتر شد به‌جای آن ۱ و اگر $i - 1$ از ۱ کمتر شد به‌جای آن $n$ را در نظر بگیرید.) می‌دانیم هزینه‌ی روشن کردن شماره‌ی $i$ برابر $c_i$ است. می‌خواهیم با کمترین هزینه ممکن، تعدادی از چراغ‌ها را روشن کنیم به طوری که محوطه‌ی زیر همه‌ی چراغ‌ها روشن باشد. # ورودی در سطر اول عدد $t$ آمده که تعداد تست‌ها را نشان می‌دهد. $$1 \leq t \leq 200 \, 000$$ در هر خط یک عدد $n$ و سپس در خط بعد $n$ عدد نشان‌دهنده‌ی میزان هزینه برای روشن کردن هر چراغ را می‌گوییم. $$1 \leq n \leq 200 \, 000$$ $$1 \leq c_i \leq 1\ 000 \, 000$$ تضمین می‌شود $\sum n$ برای همه‌ی تست‌ها حداکثر $200 \, 000$ باشد. # خروجی عدد نهایی نشان دهنده‌ی کمترین هزینه‌ای که تمام خیابان‌ها روشن شود را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 5 1 1 1 2 2 3 3 4 7 5 7 5 4 1 1 1 100 7 4 4 4 4 4 4 4 ```` ## خروجی نمونه ۱ ``` 2 3 5 100 12 ```` <details> <summary> **توضیح نمونه ۱** </summary> ---------- اگر چراغ‌های ۱ و ۳ را روشن کنیم. هزینه‌ی $c_1 + c_3 = 1 + 1 = 2$ پرداخت می‌کنیم. همچنین برای هر کدام از محوطه‌ها حداقل یک چراغ مجاورش روشن شده است. ---------- </details> <details> <summary> **توضیح نمونه ۲** </summary> ---------- روشن کردن چراغ اول برای روشن کردن تمام محوطه کافی است و هزینه‌ی روشن کردن آن $c_1 = 3$ است. ---------- </details> <details> <summary> **توضیح نمونه ۳** </summary> ---------- اگر چراغ‌های ۳ و ۵ را روشن کنیم. هزینه‌ی $c_3 + c_5 = 4 + 1 = 5$ پرداخت می‌کنیم. همچنین برای هر کدام از محوطه‌ها حداقل یک چراغ مجاورش روشن شده است. ---------- </details> <details> <summary> **توضیح نمونه ۴** </summary> ---------- در این نمونه دقیقاً یک چراغ وجود دارد. پس باید آن را روشن کنیم تا محوطه روشن شود. ---------- </details> <details> <summary> **توضیح نمونه ۵** </summary> ---------- در این نمونه ۷ چراغ داریم که هزینه‌ی روشن کردن آن‌ها برابر است. برای روشن کردن کل محوطه به روشن کردن حداقل ۳ چراغ نیاز داریم. با روشن کردن ۱، ۴ و ۷ می‌توانیم به این هدف برسیم. پس حداقل هزینه‌ی روشن کردن کل میدان برابر $c_1 + c_4 + c_7 = 4 + 4 + 4 = 12\,$ است. ---------- </details>

حل سؤال در بانک سؤالات