چهل و دو


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

آشمز که با حقوق جدیدش دنباله‌ی nn عضوی a1,a2,,ana_1, a_2, \dots, a_n\, از اعداد صحیح را خریده است، با اشتیاق دنباله‌اش را به کشی نشان داد. اما کشی در یک ضد حال به آشمز گفت تعداد ۴۲ های دنباله کم است! پس تصمیم گرفتند با انجام تعدادی عملیات دنباله را طوری تغییر دهند تا تعداد ۴۲ های آن زیاد شود.

آن‌ها می‌توانند عملیات های زیر را انجام دهند:

  • آشمز در هر عملیات می‌تواند یک پیشوند از دنباله را انتخاب و یک واحد از آن کم کند.
  • کشی در هر عملیات می‌تواند یک پسوند از دنباله را انتخاب و یک واحد از آن کم کند.

توضیح تصویر

در این سوال شما باید به آشمز و کشی کمک کنید و با ورودی گرفتن دنباله‌ی اولیه، بیشینه تعداد تکرار های ممکن ۴۲ را برای آن‌ها محاسبه کنید.

دقت کنید که ترتیب و تعداد عملیات‌ها دلخواه است و اعداد دنباله، پس از انجام یک عملیات ممکن است منفی شوند.

ورودی🔗

در سطر اول ورودی، عدد nn نشان دهنده‌ی طول دنباله آمده است. 1n14371 \leq n \leq 1437

در سطر دوم ورودی، nn عدد صحیح به نام a1,a2,,ana_1, a_2, \dots, a_n\, آمده که وضعیت اولیه دنباله را نشان می‌دهد. 1ai1091 \leq a_i \leq 10^9

خروجی🔗

در تنها سطر خروجی باید بیشینه تعداد تکرار های ممکن ۴۲ پس از انجام تعداد دلخواهی عملیات را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
43 42 43
Plain text

خروجی نمونه ۱🔗

3
Plain text

در این مثال اگر آشمز روی پیشوند به طول ۱ و کشی روی پیشوند به طول ۱ عملیات انجام دهد، تمام اعضای دنباله ۴۲ خواهند شد.

ورودی نمونه ۲🔗

7
37 42 45 45 45 42 37
Plain text

خروجی نمونه ۲🔗

4
Plain text

در این مثال اگر آشمز سه بار روی پیشوند به طول ۵ عملیات انجام دهد، دنباله به a=[34,39,42,42,42,42,37]a = [34, 39, 42, 42, 42, 42, 37] تبدیل خواهد شد که تعداد ۴۲ های آن ۴ است. می‌توان نشان داد به هر نحوی عملیات انجام دهیم، تعداد ۴۲ ها بیشتر از ۴ نخواهد شد.

ورودی نمونه ۳🔗

7
45 50 44 5 46 44 45
Plain text

خروجی نمونه ۳🔗

5
Plain text