سوال ۲

الگوریتم زیر را درنظر بگیرید:

1. آرایه‌ی $A$ به طول $n$ را ورودی بگیر.
2. اگر آرایه‌ی $A$ مرتب بود، به مرحله‌ی ۷ برو.
3. دو آرایه‌ی $X = A[1\cdots\lfloor\frac{n}{2}\rfloor]$ و $Y = A[\lfloor\frac{n}{2}\rfloor+1\cdots n]$ را درنظر بگیر.
4. عدد صحیح $t$ را ورودی بگیر؛ اگر $t$ عددی زوج بود، به مرحله‌ی ۶ برو.
5. آرایه‌ی $A$ را برابر با $X$ و مقدار $n$ را برابر با $\lfloor\frac{n}{2}\rfloor$ قرار بده. سپس به مرحله‌ی ۲ برو.
6. آرایه‌ی $A$ را برابر با $Y$ و مقدار $n$ را برابر با $n-\lfloor\frac{n}{2}\rfloor$ قرار بده. سپس به مرحله‌ی ۲ برو.
7. آرایه‌ی $A$ را خروجی بده.
8. پایان.

منظور از $A[l\cdots r]$ بازه‌ی $l$ تا $r$ از آرایه‌ی $A$ (شامل خود $l$ و $r$) است؛ برای مثال اگر $A = \langle2, 1, 3, 5, 4\rangle$ باشد $A[2\cdots4] = \langle1, 3, 5\rangle$ می‌شود. اگر مقادیر $t$ را به صورتی ورودی دهیم که طول آرایه‌ی نهایی بیشینه شود، به ازای چند جایگشت اولیه از اعداد ۱ تا ۸ طول آرایه‌ی نهایی حداقل برابر با ۲ خواهد بود؟

1. ۲۰۱۶۰
2. ۴۰۳۲۰
3. ۳۴۵۱۰
4. ۳۰۲۴۰
5. ۳۷۸۰۰