Bessie ו־Canmuu מצאו שק עם $N$ מטבעות זהב ($1 \leq N \leq 250$) ורוצות לחלקו באופן שווה ככל האפשר. למטבע $i$ ערך $v_i$ ($1 \leq V_i \leq 2{,}000$). הפרות רוצות שתי ערימות שוות ערך, אך לא תמיד אפשר. מה ההפרש המזערי בין הערכים?

ייתכנו כמה חלוקות עם ההפרש המזערי. הן רוצות גם לדעת את מספר החלוקות ההוגנות ביותר. אם שוויון אינו אפשרי, Bessie תקבל את הערימה היקרה יותר.

למשל חמישה מטבעות בערכים $2, 1, 8, 4, 16$. בערימה אחת מטבע $16$, ובאחרת השאר בערך $1+2+4+8=15$. ההפרש $16-15 = 1$. זו החלוקה היחידה כך, ולכן מספר החלוקות השוות ככל האפשר הוא $1$.

החלפת מטבעות בעלי אותו ערך בין הערימות מגדילה את מספר החלוקות המיטביות. לכן $\{1, 1, 1, 1\}$ מאפשר שש חלוקות מיטביות שונות, שני מטבעות בכל ערימה.

קלט

קראו מהקלט התקני.

• שורה $1$: שלם אחד $N$.

• שורות $2..N+1$: בשורה $i+1$ שלם אחד $V_i$.

פלט

כתבו לפלט התקני.

• שורה $1$: שלם, ההפרש המזערי בין ערכי הערימות.

• שורה $2$: מספר החלוקות עם ההפרש המזערי שבשורה הראשונה. המספר עשוי להיות גדול; הדפיסו את השארית בחלוקה ב־$1,000,000$.

דוגמאות

קלט 1

5
2
1
8
4
16

פלט 1

1
1

קרדיט: Sherry Wu, בעיה קלאסית, 2010