+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- تعدادی ماهی در یک صف قرار گرفته‌اند. وزن هر ماهی به جز ماهی اول مشخص است و وزن ماهی $i$م برابر با $a_i$ است. ماهی $i$ می‌تواند ماهی $j$ را بخورد اگر و تنها اگر $a_j \leq a_i \ $، درصورتی که ماهی $i$ ماهی $j$ را بخورد وزن ماهی $i$ در نهایت برابر با مجموع وزن دو ماهی خواهد شد و ماهی $j$ دیگر در صف نخواهد بود. تا زمانی که بیش از یک ماهی در صف باقی مانده باشد، دو مرحلهٔ زیر به‌ترتیب اجرا می‌شوند: + ابتدا ماهی اول تلاش می‌کند تنها ماهی مجاور خود را بخورد. اگر ماهی اول نتواند ماهی جلوی خود را بخورد، بازی به پایان می‌رسد و او بازنده خواهد شد. + امیرحسین که از ماهی اول متنفر است، می‌تواند تعدادی جفت از ماهی‌های باقی‌مانده(شامل ماهی اول) را انتخاب کند (او می‌‌تواند هیچ جفتی انتخاب نکند)، به‌طوری‌که هر ماهی حداکثر در یک جفت قرار بگیرد و دو ماهیی که مجاور یکدیگر نیستند در یک جفت قرار نگیرند. سپس در هر جفت، امیرحسین ماهی سنگین‌تر را مجبور می‌کند جفت سبک‌تر خود را بخورد (اگر وزن دو ماهی برابر باشد یکی از آنها به انتخاب امیرحسین دیگری را می‌خورد). امیرحسین که کمر به نابودی ماهی اول بسته می‌خواهد کمترین عدد طبیعی $x$ را بداند به طوری که اگر وزن ماهی اول $x$ باشد $(a_1=x) \ $، امیرحسین در بازی هرطور جفت ها را انتخاب کند باز تنها ماهی باقی مانده در آخر بازی ماهی اول خواهد بود. # ورودی در خط اول، عدد صحیح $n$، تعداد ماهی‌ها، داده می‌شود. در خط دوم، $n-1$ عدد صحیح داده می‌شود که به‌ترتیب وزن ماهی‌های دوم تا $n$م را نشان می‌دهند. $$ 1 \leq n \leq 3*10^5 $$ $$ 1 \leq a_i \leq 10^9 $$ # خروجی در تنها خط خروجی، کمترین مقدار ممکن برای وزن اولیه‌ی ماهی اول را چاپ کنید؛ به‌طوری‌که ماهی اول در هر صورت توسط ماهی دیگری خورده نشود. # مثال ## ورودی نمونه ۱ ``` 3 3 7 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 6 7 1 10 6 8 ``` ## خروجی نمونه ۲ ``` 16 ```