Ta nhận thấy, tổng độ dài của các dãy con tăng ngặt dài nhất kết thúc tại ~i~ đạt được khi dãy đó được sắp xếp tăng dần. Vì vậy, ta có cách làm như sau:

• Sắp xếp mảng tăng dần.
• Duyệt từ ~1~ đến ~n~, với mỗi ~i~ ta cộng thêm vào kết quả tích của số lần xuất hiện của phần tử thứ ~i~ với số phần tử khác nhau từ ~1~ đến ~i~.

Lưu ý: Với mỗi phần tử khác nhau chỉ cộng một lần.

Code mẫu

#include <bits/stdc++.h>
#define int long long 
#define ii pair<int,int>
#define st first
#define nd second
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
int n, a[MAXN];
void program(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort (a + 1, a + n + 1);
    map<int,int> m;
    int ans = 0;
    for (int i = 1; i <= n; i++){
        m[a[i]]++;
        ans += (int)m.size();
    }
    cout << ans << endl;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int test = 1;
    while (test --> 0){
        program();
    }
}