Olkoon $B$ pituutta $M$ oleva taulukko, joka koostuu positiivisista kokonaisluvuista.
Yhdessä operaatiossa voit valita indeksien epätyhjän alijonon$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$ siten, että arvot $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ ovat pareittain eri suuria, ja vähentää sitten jokaista valittua arvoa luvulla $1$.
Määritellään taulukon $B$ pistemäärä, jota merkitään $\text{score}(B)$, pienimmäksi operaatioiden määräksi, joka tarvitaan muuttamaan jokainen taulukon $B$ alkio luvuksi $0$.
Annettuna on pituutta $N$ oleva taulukko $A$.
Etsi pistemäärien summa yli kaikkien taulukon $A$ epätyhjien alijonojen.
Koska arvo voi olla suuri, tulosta se modulo $998\,244\,353$.
$^\dagger$ Jonoa $C$ kutsutaan jonon $D$ alijonoksi, jos se voidaan saada jonosta $D$ poistamalla useita alkioita (mahdollisesti ei yhtään tai kaikki) muuttamatta jäljelle jäävien alkioiden järjestystä.
Syöte
Syöte annetaan seuraavassa muodossa:
T N A_1 A_2 ... A_N :
- Kaikki syötteen arvot ovat kokonaislukuja.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- On taattu, että lukujen $N^2$ summa yli kaikkien testitapausten ei ylitä arvoa $5000^2$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi kokonaisluku — pistemäärien summa yli kaikkien taulukon $A$ epätyhjien alijonojen, modulo $998\,244\,353$.
Esimerkit
Esimerkkisyöte 1
3 1 5 3 1 1 3 4 2 2 2 2
Esimerkkituloste 1
5 16 47
Huomautus
Testitapaus 1: Ainoa epätyhjä alijono on $[5]$, jonka pistemäärä on $5$. Siispä vastaus on $5$.
Testitapaus 2: Taulukon $[1, 1, 3]$ epätyhjät alijonot ovat:
- kaksi alijonoa, jotka ovat $[1]$, kummankin pistemäärä on $1$,
- $[3]$, jonka pistemäärä on $3$,
- $[1, 1]$, jonka pistemäärä on $2$,
- kaksi alijonoa, jotka ovat $[1, 3]$, kummankin pistemäärä on $3$,
- $[1, 1, 3]$, jonka pistemäärä on $3$.
Kokonaispistemäärä on siis $16$.