CUBE-194: Déjà vu

#include <bits/stdc++.h>

using namespace std;

using lli = long long;
const lli INF = 2e18;

int dp[100001];
lli sum[100001];

int main(){

    int n;
    scanf("%d", &n);

    lli ar[n+1];

    for(int i=1;i<=n;i++) scanf("%lld", &ar[i]);

    int sz = 0;
    dp[0] = INF;
    sum[0] = 0;

    for(int i=n;i>=1;i--){

        if(ar[i] <= dp[sz]){
            sz ++;
            dp[sz] = ar[i];
            sum[sz] = sum[sz-1] + ar[i];
        }

        else {
            int l = 1, r = sz, mn = INF;
            while(l <= r){
                int mid = (l + r) / 2;
                if(ar[i] > dp[mid]){
                    r = mid - 1;
                    mn = min(mn, mid);
                }
                else {
                    l = mid + 1;
                }
            }
            dp[mn] = ar[i];
            sum[mn] = sum[mn-1] + ar[i];
        }

    }

    printf("%d %lld", sz, sum[sz]);

    return 0;
}