Látum $B$ vera fylki af lengd $M$ sem samanstendur af jákvæðum heiltölum.
Í einni aðgerð máttu velja ótóma hlutrunu$^\dagger$ af vísum $1 \le i_1 < i_2 < \dots < i_k \le M$ þannig að gildin $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ séu innbyrðis ólík, og minnka síðan hvert valið gildi um $1$.
Skilgreinum stig fylkisins $B$, táknað með $\text{score}(B)$, sem minnsta fjölda aðgerða sem þarf til að gera hvert stak í $B$ jafnt $0$.
Gefið er fylki $A$ af lengd $N$.
Finndu summu stiga yfir allar ótómar hlutrunur fylkisins $A$.
Þar sem gildið gæti verið stórt skaltu prenta það módulo $998\,244\,353$.
$^\dagger$ Runa $C$ kallast hlutruna runu $D$ ef hægt er að fá hana úr $D$ með því að eyða nokkrum stökum, hugsanlega engu eða öllum, án þess að breyta röð þeirra staka sem eftir standa.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T N A_1 A_2 ... A_N :
- Öll inntaksgildi eru heiltölur.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Tryggt er að summa $N^2$ yfir öll prófunartilvik fari ekki yfir $5000^2$.
Úttak
Fyrir hvert prófunartilvik skaltu prenta eina heiltölu — summu stiga yfir allar ótómar hlutrunur fylkisins $A$, módulo $998\,244\,353$.
Dæmi
Dæmi um inntak 1
3 1 5 3 1 1 3 4 2 2 2 2
Dæmi um úttak 1
5 16 47
Athugasemd
Prófunartilvik 1: Eina ótóma hlutrunan er $[5]$, með stig $5$. Því er svarið $5$.
Prófunartilvik 2: Ótómu hlutrunurnar í $[1, 1, 3]$ eru:
- tvær hlutrunur jafnar $[1]$, hvor um sig með stig $1$,
- $[3]$, með stig $3$,
- $[1, 1]$, með stig $2$,
- tvær hlutrunur jafnar $[1, 3]$, hvor um sig með stig $3$,
- $[1, 1, 3]$, með stig $3$.
Heildarsumman er því $16$.