+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --------- زنگ تفریح بعد از کلاس هنر پوریا و هم کلاسی هایش تصمیم گرفتند بازی ای بکنند. همه $N$ دانش آموزان کلاس پشت سر هم بر روی یک صف قرار گرفتند. برای مثال دانش آموز 2 پشت 1 و 3 پشت 2 و به همین ترتیب تا آخر. شادی یک دانش آموز $i$ ام را اینگونه تعریف میکنیم: تعداد دانش آموزانی که مقابل او قرار دارند و قدشان از او (دانش آموز $i$ام) اکیدا بلند تر است. خوشی یک کلاس برابر جمع کل شادی های همه دانش آموزان کلاس. شما که دیگر از دست پوریا خسته شده اید میخواهید از او انتقام بگیرید قرار است خوشی کلاس را کمینه کنید تا حال پوریا گرفته شود! دقت کنید که شما می‌توانید یک دانش آموز را از هر جا را انتخاب کنید و اورا به آخر صف ببرید. # ورودی در خط اول عدد $T$ داده می‌شود $$1 \le T \le 5$$ در $T$ خط بعدی برای هر خط یک عدد $N$ داده می‌شود که تعداد دانش آموزان است و در خط بعد یک لیستی از $N$ عدد که نشان دهنده قد هر دانش آموز است $h_i$. $$1 \le N \le 10^5$$ $$1 \le h_i \le 10^{10}$$ # خروجی برابر هر ورودی نمونه، کمینه خوشی که می‌توانید ایجاد کنید را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 4 4 1 3 2 ``` ## خروجی نمونه ۱ ``` 1 ```