CSES - Alijonot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Sinulla on taulukko, jossa on nn kokonaislukua, ja haluat laskea, montako nousevaa alijonoa taulukossa on.

Nouseva alijono sisältää joukon taulukon alkioita vasemmalta oikealle niin, että jokainen alkio on suurempi kuin edellinen alkio.

Huomaa, että jos kaksi alijonoa sisältävät samat luvut mutta eri kohdista otettuina, ne lasketaan erikseen.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: taulukon koko.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\dots,x_n: taulukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: nousevien alijonojen määrä modulo 109+710^9+7.

Rajat

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1xi1091 \le x_i \le 10^9

Esimerkki

Syöte:

3
2 1 3

Tuloste:

5

Selitys: Alijonot ovat [2][2], [1][1], [3][3], [2,3][2,3] ja [1,3][1,3].