داوینچی

لئوناردو داوینچی وارد دنیای علوم کامپیوتر شده است و روی آرایه‌ها کار می‌کند. او در جهت زیبا کردن آرایه، حرکت طلایی زیر را روی آن انجام می‌دهد.

• در یک حرکت طلایی دو عدد $x$، $x+1$ را به همین ترتیب انتخاب می‌کند، سپس آن دو را با عدد $x+2$ جایگزین می‌کند. دقت کنید که پس از حرکت طلایی تعداد اعضای آرایه منهای یک می‌شود و اعضا دوباره کنار هم قرار می‌گیرند.

داوینچی به یک آرایه می‌گوید طلایی، اگر با دنباله‌ای از حرکات طلایی بتوان به تنها یک عدد رسید. همچنین زیبایی یک آرایه طلایی را مقدار آن عدد نهایی تعریف می‌کند. او اثبات کرده است که اگر یک آرایه طلایی باشد، زیبایی آن یکتا است. به داوینچی کمک کنید و سوالات زیر که در رابطه با آرایه‌های طلایی هستند را حل کنید!

برای مثال اگر از آرایه‌ی $\langle 3,2,3\rangle$ شروع کنیم و روی دو عضو آخر آن حرکت طلایی انجام دهیم به $\langle 3,4\rangle$ تبدیل می‌شود و نهایتاً اگر روی این دو عدد حرکت انجام بدهیم به $\langle 5\rangle$ تبدیل می‌شود. پس آرایه‌ی اولیه آرایه‌ای طلایی با زیبایی ۵ بود. اما آرایه‌ی $\langle 3,3,2,4\rangle$ طلایی نیست چون روی هیچ دو عضو متوالی نمی‌توان حرکت طلایی انجام داد.

ورودی

در فایل array.txt یک آرایه‌ی طلایی به سایز $10^5$ در یک خط آمده است. تضمین داده می‌شود اعضای این آرایه عددی در بازه‌ی $1$ تا $10^9$ هستند و با دنباله‌ای از حرکات طلایی می‌توان به تنها یک عدد رسید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$1$- الف ($11$ نمره) : زیبایی آرایه‌ی ۲۰ تایی زیر چقدر است؟

$45, 44, 45, 46, 47, 48, 49, 50, 51, 46, 47, 47, 48, 45, 46, 44, 45, 47, 50, 53$

$1$- ب ($23$ نمره) : زیبایی آرایه‌ای که در فایل آمده است به پیمانه‌ی $\Delta$ چقدر است؟

$1$- ج ($34$ نمره) : تعداد آرایه‌های طلایی به طول ۴۰۲ که اعضایشان عددی در بازه‌ی ۱ تا ۱۴۰۲ باشد به پیمانه‌ی $\Delta$ چقدر است؟

$1$- د ($32$ نمره) : تعداد جایگشت‌های طلایی آرایه‌ای که در فایل آمده است به پیمانه‌ی $\Delta$ چقدر است؟ دو عدد برابر در آرایه را یکسان در نظر می‌گیریم، و برای ترتیب آن‌ها تمایز قائل نمی‌شویم.