- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
تاجر ثروتمندی به نام سینا صاحب یک ردیف شامل \(n\) خانه متوالی به شمارههای \(1\) تا \(n\) است. ارزش خانه \(i\)ام برابر با \(a_i\) است.
سینا میخواهد این ردیف را به \(4\) بخش متوالی افراز کند و به هر یک از \(4\) فرزند خود یکی از این بخشها را به عنوان میراث بدهد.
همچنین او قصد دارد به طور عادلانه اینکار را انجام دهد. برای انجام این کار، سینا نیازمند است تا کمترین میزان اختلاف ممکن بین فرزندی که بیشترین ارث را میبرد با فرزندی که کمترین ارث را میبرد، مشخص کند.
به سینا کمک کنید تا وصیتنامه خود را بنویسد.
ورودی
در خط اول عدد \(n\) داده میشود.
سپس، در خط بعدی \(n\) عدد که نشانگر دنباله \(a_i\)ها است میآیند.
خروجی
در تنها خط خروجی، کمترین اختلاف ممکن ارزش ارث بین فرزند با بیشترین ارث و فرزند با کمترین ارث را چاپ کنید.
محدودیتها
- \(4 \leq n \leq 2 \times 10^5\)
- \(1 \leq a_i \leq 10^9\)
مثالها
ورودی نمونه ۱
5
6 4 8 2 4
خروجی نمونه ۱
4
ورودی نمونه ۲
10
20 142 168 66 12 94 46 50 104 128
خروجی نمونه ۲
72
ورودی نمونه ۳
7
3 8 2 1000000000 9 2 1
خروجی نمونه ۳
999999997
ارسال پاسخ برای این سؤال