#include<bits/stdc++.h>
#define LL long long
#define N ((int)1e5 + 8)
#define MAX ((int)1e9 + 8)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)

using namespace std;

int GetLeft(int n)
{
    n = FindPar(n);
    return leftIndex[n];
}

int GetMax(int n)
{
    n = FindPar(n);
    return maxH[n];
}

void Merge(int a , int b)
{
    a = FindPar(a) , b = FindPar(b);
    par[a] = b;
    maxH[b] = max(maxH[a] , maxH[b]);
    lefIndex[b] = min(leftIndex[a] , leftIndex[b]);
}

int main()
{
    /// seg(i) => dp[i-1] + max(i , ... , cur)
    dp[0] = 0;

    for(int i = 1 ; i <= n ; i++){
        leftIndex[i] = i;
        par[i] = i;
        maxH[i] = arr[i];
    }

    leftEnd[1] = 1;
    vis[type[1]] = 1;
    for(int i = 2  ; i <= n ; i++){
        if(vis[type[i]] == 0) leftEnd[i] = leftEnd[i-1];
        else{
            for(int j = leftEnd[i-1] ; j <= i ; j++){
                if(vis[type[i]] == 0){
                    leftEnd[i] = j;
                    break;
                }
                vis[type[j]] = 0;
            }
        }

        vis[type[i]] = 1;
    }

    for(int cur = 1 ; cur <= n ; cur++){
        for(int i = cur-1 ; i > 0 && GetMax(i) <= arr[cur]; i = GetLeft(i) - 1){
            int from = GetLeft(i);
            Update(from , i , -GetMax(i) + arr[cur]);
            Merge(i , cur);
        }
        Update(cur , cur , arr[cur] + dpp[cur-1]);
        dpp[i] = Query(leftEnd[cur] , cur);
    }
}