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

Sinulla on taulukko, jossa on n 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 n: taulukon koko.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\dots,x_n: taulukon sisältö.

Tuloste

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

Rajat

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

Esimerkki

Syöte:

3
2 1 3

Tuloste:

5

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