#include "friend.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define pb push_back;
const int nax = 1e5;
ll dp[nax+5];
ll tree[4*nax+5];
int n;
void upd(int idx, int l, int r, int where) {
if(l == r && l == where) tree[idx] = dp[where];
else if (l <= where && where <= r) {
int m = (l+r)>>1;
upd(idx<<1, l, m, where);
upd(idx<<1|1, m+1, r, where);
tree[idx] = max(tree[idx<<1], tree[idx<<1|1]);
}
}
ll query(int idx, int l, int r, int from, int to) {
if(to < l || from > r) return 0;
else if (l <= from && to <= r) return tree[idx];
else {
int m = (l+r) >> 1;
return max(query(idx<<1, l, m, from, to), query(idx<<1|1, m+1, r, from, to));
}
}
ll get (int l, int r) {
if(r < l) return 0;
return query(1, 0, n-1, l, r);
}
// Find out best sample
int findSample(int N,int confidence[],int host[],int protocol[]){
n = N;
dp[0] = confidence[0];
ll ans = dp[0];
for(int i=1; i<N; i++) {
dp[i] = confidence[i] + max(get(0, host[i]-1), get(host[i]+1, i));
upd(1, 0, n-1, i);
ans = max(ans, dp[i]);
}
return ans;
}
