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

چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید.

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

از آن‌جایی که چرزه یک آدم الگوریتمی است، جان او به صورت یک دنباله‌ی $n$ تایی خفن است. اما به چه دنباله‌ای خفن می گوییم؟

قبل از دانستن دنباله‌ی خفن باید تعریف دنباله‌ی چراهام پل را بدانید. فرض کنید که یک دنباله از اعداد طبیعی مانند $a$ داشته باشیم. از روی این دنباله یک دنباله از اعداد حسابی به نام $t$ به این صورت می‌سازیم که $t_i$ برابر است با تعداد $a_j$ ها به صورتی که:

• $i \neq j$
• $gcd(a_i,a_j) = 1$

برای مثال اگر دنباله‌ی $a$ ما $\left[1, 3,6 \right]$ باشد، دنباله‌ی $t$، $\left[2, 1, 1 \right]$ می‌باشد. در این جا می‌گوییم دنباله‌ی $t$ دنباله‌ی چراهام پل دنباله‌ی $a$ است.

اکنون به دنباله‌ی خفن باز می‌گردیم؛ یک دنباله از اعداد حسابی خفن است اگر و تنها اگر که بتوان آن را به صورت دنباله‌ی چراهام پل حداقل $1381$ دنباله از اعداد طبیعی نوشت؛ یعنی یک دنباله از اعداد حسابی مانند $z$ خفن است اگر و تنها اگر حداقل $1381$ دنباله از اعداد طبیعی مانند $tmp$ وجود داشته باشد که دنباله‌ی چراهام پل $tmp$، دنباله‌ی $z$ باشد. برای مثال دنباله‌ی $\left[2, 1, 1 \right]$ یک دنباله‌ی خفن است.

داعشی‌ها که می‌خواستند چرزه را آزار بدهند، به او گفتند که اگر به مساله‌‌شان پاسخ بدهد، جان او را بهش پس می دهند. اما چون چرزه جان ندارد نمی‌تواند خوب فکر کند، پشمک هم که برنامه‌نویسی زیاد بلد نیست بنابراین حل سوال داعشی‌ها به شما واگذار می‌شود:

یک‌دنباله از اعداد حسابی (که ممکن است خفن نباشد) به شما می‌دهیم. شما باید حداکثر تعداد دنباله‌های زیرینه‌ی دو به دو متفاوت از این دنباله را بگویید که خودشان خفن هستند!

توجه کنید که دو دنباله‌ی $a$ و $b$ متفاوت هستند اگر و تنها اگر $\sum a_i$ با $\sum b_i$ متفاوت باشد.

هم چنین دنباله‌ی $a$ زیرینه‌ی دنباله‌ی $b$ است، اگر و تنها اگر سه شرط زیر برقرار باشد:

1. دنباله‌ی $a$ و $b$ متفاوت باشند.
2. داشته باشیم $|a| = |b|$
3. به ازای هر $1 \leq i \leq |a|$ داشته باشیم $a_i \leq b_i$

ورودی

در خط اول یک عدد $n$ داده می‌شود که طول دنباله‌ی داعشی‌ها است.

در خط بعد $n$ عدد حسابی داده می‌شود که دنباله‌ی داعشی‌ها است. (یعنی دنباله‌ی $a$) $$1 \leq n \leq 3000$$ $$0 \leq a_i \leq 10^{9}$$

خروجی

در یک خط حداکثر تعداد دنباله‌های دو به دو متفاوت خفن زیرینه‌ی دنباله‌ی ورودی را چاپ کنید.

مثال

ورودی نمونه ۱

3
2 2 1

خروجی نمونه ۱

3

ورودی نمونه ۲

3
1 0 1

خروجی نمونه ۲

1

توضیح

برای مثال اول، یک راه برای نوشتن دنباله‌های دو به دو متفاوت زیرینه‌ی خفن به این صورت است:

$$\left[2, 1, 1 \right]$$ $$\left[1, 1, 0 \right]$$ $$\left[0, 0, 0 \right]$$

هم‌چنین برای مثال دوم، تنها دنباله‌ی زیرینه‌ی خفن دنباله‌ی ورودی،

$$\left[0, 0, 0 \right]$$

می‌باشد.