Metal Processing Plant

//misaka and elaina will carry me to master
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>
#include <numeric>
#include <set>
#include <array>
#include <queue>
#include <map>
#include <chrono>
#include <random>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define kill(x, s) {int COND = x; if(COND){ cout << s << "\n"; return ; }}

#ifdef ONLINE_JUDGE
#define cerr while(0) cerr
#endif

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 400 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;

vector<int> rel;

vector<int> adj[MX], adj2[MX], tr[MX];
vector<int> scc[MX];
vector<array<int, 3>> edges;
int n;
int id[MX];
int vis[MX];
vector<int> comp, order;
int tim = 0;

#define LC(k) (k)
#define RC(k) (k + n)

void add_or(int x, int y){
    adj[RC(y)].pb(LC(x));
    adj[RC(x)].pb(LC(y));
    adj2[LC(y)].pb(RC(x));
    adj2[LC(x)].pb(RC(y));
}

void add_xor(int x, int y){
    adj[LC(x)].pb(RC(y));
    adj[RC(x)].pb(LC(y));
    adj[LC(y)].pb(RC(x));
    adj[RC(y)].pb(LC(x));
    adj2[LC(x)].pb(RC(y));
    adj2[RC(x)].pb(LC(y));
    adj2[LC(y)].pb(RC(x));
    adj2[RC(y)].pb(LC(x));
}

void dfs1(int u){
    vis[u] = 1;
    for(int v : adj[u]){
        if(!vis[v]){
            dfs1(v);
        }
    }
    order.pb(u);
}

void dfs2(int u, int s){
    vis[u] = 1;
    scc[s].pb(u);
    comp.pb(u);
    for(int v : adj2[u]){
        if(!vis[v]){
            dfs2(v, s);
        }
    }
}


int check(int x, int y){
    for(int i = 0; i<=n*2+4; i++){
        adj[i].clear();
        adj2[i].clear();
        scc[i].clear();
        id[i] = 0;
    }
    order.clear();
    comp.clear();
    memset(vis, 0, sizeof(vis));
    for(auto [w, u, v] : edges){
        if(w > max(x, y)){
            add_xor(u, v);
        }else if(w > min(x, y)){
            add_or(u, v);
        }
    }
    for(int i = 1; i<=n*2; i++){
        if(!vis[i]){
            dfs1(i);
        }
    }
    reverse(all(order));
    memset(vis, 0, sizeof(vis));
    for(int x : order){
        if(!vis[x]){
            dfs2(x, x);
        }
    }
    for(int i = 1; i<=n*2; i++){
        for(int v : scc[i]){
            id[v] = i;
        }
    }
    for(int i = 1; i<=n; i++){
        if(id[i] == id[i + n]) return 0;
    }
    return 1;
}

int binsearch(int x){
    int l = -1, r = 1e9 +10;
    while(l + 1 != r){
        int mid = (l + r)/2;
        if(!check(x, mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    return l + x + 1;
}

int yy[MX], cc[MX];

int find(int x){
    if(x == yy[x]) return x;
    return yy[x] = find(yy[x]);
}

void Union(int a, int b){
    a = find(a), b = find(b);
    yy[a] = b;
}

void color(int u, int p){
    cc[u] = cc[p]^1;
    for(int v : tr[u]){
        if(v != p) color(v, u);
    }
}

int last_case(){
    color(1, 0);
    array<int, 2> D = {0, 0};
    for(auto [w, u, v] : edges){
        if(cc[u] == cc[v]){
            D[cc[u]] = max(D[cc[u]], w);
        }
    }
    rel.pb(max(D[1], D[0]));
    return D[0] + D[1];
}

void solve(){
    n = in;
    kill(n <= 2, 0);
    for(int i = 1; i<=n-1; i++){
        for(int j = i+1; j<=n; j++){
            int a = in;
            edges.pb({a, i, j});
        }
    }
    sort(all(edges));
    reverse(all(edges));
        iota(yy+1, yy+1+n, 1);
    for(auto [w, u, v] : edges){
        //rel.pb(w);
        if(find(u) != find(v)){
            rel.pb(w);
            Union(u, v);
            tr[u].pb(v);
            tr[v].pb(u);
        }
    }
    int ans = int_max*2;
    last_case();
    sort(all(rel));
    rel.resize(unique(all(rel)) -rel.begin());
    for(int x : rel){
        if(x >= ans) continue ;
        ans = min(ans, binsearch(x));
    }
    cout << ans << "\n";
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);

  int T = 1;
  //cin >> T;
  for(int i = 1; i<=T; i++){
        solve();
    }
  return 0;
}