ボールが完全にソートされる時刻は、全てのボールが「自身より軽いボール全てよりも下にある」状態（状態Aとします）となった時刻です。そのため、各ボールについてこの状態に達する時刻を求めると、その最大値が答えです。

重さ \(0\) のボールについては考える必要はないので、正の重さを持つボールについて考えます。ボールの動きを観察すると、以下のことがわかります。

• ある時刻から、マスの番号を \(j\) として、\(t-j\) が一定の線に乗って上半分の領域（ \(1\leq j\leq N\) である領域）から下半分の領域（ \(N+1\leq j\leq 2N\) である領域）に突入し、そのまま状態Aになるまで \(j\) が増加する。

各ボールに対して、上記の \(t-j\) の値を定めていきます。

まず、最も重いボールは初期配置での値をそのまま採用できます。この際、この値の \(\pm 1\)の範囲は、このボールが下に移動する際に浮き上がるボールが占めるため、以降 \(\pm 1\) の範囲の \(t-j\) を採用できないことが決まります。次に重いボールは、この範囲に入っていなければそのまま初期配置での値を採り、そうでなければそれ以上で採用できる最も小さな値を採ることになります。動きが未確定のボールは全てこれより軽いため、その動きが可能であることが保証されます。これを繰り返すと、全てのボールに対して \(t-j\) の値が求まります。

次に各ボールが状態Aになる時刻を求めます。そのためには、各ボールが \(t-j\) 一定の軌道に乗った際に、それより下にある自身より重いボールの数を求めれば良いです。

ところで、\(t-j\) の定め方より、\(t-j\) の最大値は必ず \(N-2\) 以上であることが分かります。そのため、この \(t-j\) に割り当てられたボールが正の重さの中で最も軽く、\(j=N+1\) で状態Aになるとしても、その時刻は \(2N-1\) 以上です。\(t-j\) が負の範囲では、\(j=2N\) まで状態Aにならないとしてもその時刻は \(2N-1\) 以下であるため、\(0\) 以上の \(t-j\) に割り当てられるボールのみに対して時刻を求めれば十分です。

さらに、\(t-j\) が \(0\) 以上となる領域では、単にボールの重さの降順に \(t-j\) が並んでいることも分かります。そのため、この領域では自身より重いボールは全て先に沈んでおり、単に \(j=N+w\) （ \(w\) は自身の重さ）で状態Aになることが分かります。

なお、後半の考察を飛ばして、セグメント木などを用いて全てのボールに対する「それより小さな \(t-j\) に乗っている自身より重いボールの数」を求めることもできます。

以上より答えが求まります。

実装例：https://atcoder.jp/contests/arc188/submissions/60033454