ليكن $B$ مصفوفة طولها $M$ تتكون من أعداد صحيحة موجبة.
في عملية واحدة، يمكنك اختيار متتالية فرعية غير فارغة$^\dagger$ من الأدلة $1 \le i_1 < i_2 < \dots < i_k \le M$ بحيث تكون القيم $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ مختلفة مثنى مثنى، ثم إنقاص كل قيمة مختارة بمقدار $1$.
نعرّف نتيجة $B$، ويرمز إليها بـ $\text{score}(B)$، بأنها أقل عدد من العمليات اللازمة لجعل كل عنصر في $B$ مساوياً لـ $0$.
تُعطى مصفوفة $A$ طولها $N$.
أوجد مجموع النتائج عبر جميع المتتاليات الفرعية غير الفارغة من $A$.
بما أن القيمة قد تكون كبيرة، اطبعها بباقي القسمة على $998\,244\,353$.
$^\dagger$ تُسمى المتتالية $C$ متتالية فرعية من المتتالية $D$ إذا كان من الممكن الحصول عليها من $D$ بحذف عدة عناصر (ربما لا شيء أو جميعها) دون تغيير ترتيب العناصر المتبقية.
الإدخال
يُعطى الإدخال بالصيغة التالية:
T N A_1 A_2 ... A_N :
- جميع قيم الإدخال هي أعداد صحيحة.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- من المضمون أن مجموع $N^2$ عبر جميع حالات الاختبار لا يتجاوز $5000^2$.
الإخراج
لكل حالة اختبار، اطبع عدداً صحيحاً واحداً — مجموع النتائج عبر جميع المتتاليات الفرعية غير الفارغة من $A$، بباقي القسمة على $998\,244\,353$.
أمثلة
مثال الإدخال 1
3 1 5 3 1 1 3 4 2 2 2 2
مثال الإخراج 1
5 16 47
ملاحظة
حالة الاختبار 1: المتتالية الفرعية الوحيدة غير الفارغة هي $[5]$، ونتيجتها $5$. لذلك، الإجابة هي $5$.
حالة الاختبار 2: المتتاليات الفرعية غير الفارغة للمصفوفة $[1, 1, 3]$ هي:
- متتاليتان فرعيتان تساويان $[1]$، نتيجة كل منهما $1$،
- $[3]$، ونتيجتها $3$،
- $[1, 1]$، ونتيجتها $2$،
- متتاليتان فرعيتان تساويان $[1, 3]$، نتيجة كل منهما $3$،
- $[1, 1, 3]$، ونتيجتها $3$.
لذلك، المجموع الكلي هو $16$.