+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
میدان اصلی شهر کدکاپ بسیار بزرگ است. دور این میدان $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>