Cerința

Se citeşte n şi un vector v cu n numere naturale. Să se calculeze numărul total S de subşiruri strict crescătoare care se pot forma folosind aceste numere.

Date de intrare

Fișierul de intrare nrsubsircresc.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire nrsubsircresc.out va conţine numărul S cu semnificaţia din enunt.

Restricții și precizări

• 1 ≤ n ≤ 300
• v[i] ≤ 1.000.000, pentru oricare 1 ≤ i ≤ n
• S ≤ 1018

Exemplu

nrsubsircresc.in

6
5 2 6 1 1 8

nrsubsircresc.out

15

Explicație

Cele 15 subşiruri strict crescătoare sunt: {5}, {2}, {6}, {1}, {1}, {8}, {5, 6}, {5, 8}, {2, 6}, {2, 8}, {6, 8}, {1, 8}, {1, 8}, {5, 6, 8}, {2, 6, 8}.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("nrsubsircresc.in");
ofstream cout("nrsubsircresc.out");

int n , a[302];
long long sum , s[302];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i] , s[i] = 1;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= i ; j++)
            if(a[j] < a[i]) s[i] += s[j];

    for(int i = 1 ; i <= n ; i++)
        sum += s[i];

    cout << sum;
}