$O(N^2 \log N)$ の解法を紹介します。
最初に、 $i_1 < i_2 < \cdots < i_n$ 番目にいる人を $j,j+1,\cdots,j+n-1$ 番目に身長が降順となるように並べることを考えます。 $d= \sum_{K=1}^n |i_K- \left( j+K-1 \right)|$ とし、 $inv$ を $\left( H_{i_1},H_{i_2}, \cdots , H_{i_n} \right)$ の各項を $-1$ 倍したものの転倒数とします。なお、これは元の数列においてindexと値の大小関係が同じものの個数に等しいです。

ここで、 $d+inv$ 回の操作が必要かつこれで十分であることがいえます。実際、注目している $n$ 項の間のswapは $d$ は減少せず $inv$ は高々 $1$ 減少し、そうでないswapは $d$ が高々 $1$ 減少し、 $inv$ は変化しないため、 $d+inv$ 回の操作は必要です。
また、 $d$ 回の操作で注目している $n$ 項を位置関係を保ったまま $j,j+1,\cdots,j+n-1$ 番目に移動し、その後 $inv$ 回の $n$ 項の間のswapを行えば条件を達成できます。これらより示されます。

さて、ここで条件を満たした状態の身長を考えると $\left( 1,2,\cdots,N \right)$ を $1$ つ以上の区間に分割し、それの内部をreverseしたものとなります。
そこで、 $dp[i]$ を左の $i$ 人の身長が $1$ から $i$ の並び替えとなっている(かつ条件を満たす)もののうち操作回数が最小となるものとします。便宜上 $dp[0]=0$ とし、また答えは $dp[N]$ です。

\(dp[i]\) から \(dp[j]\) への遷移を考えます。 \(\left( i<j \right)\)
具体例として \(j=6\) とします。 \(i=3\) として、 \(dp[j]\) と \(dp[i]\) の差分は左から \(i\) 番目を整理した後の \(4,5,6\) のindex、 \(4,5,6\) の \(inv\) があれば求まります。

\(i\) を \(0\) から \(5\) まで動かして同様に考えると、求めたいものは \(i+1\) から \(j\) までの人に対応する \(inv\) と、 \(i\) までを左に寄せた時の \(i+1\) から \(j\) までの人に対応するindexです。

ここで \(d\) の式に登場する絶対値について、 \(dp\) の遷移においてはこれを外して計算しても問題ないことが分かります。例えば \(i=3,j=6\) の例においては \(4,5,6\) の人が \(3\) 番目より左にいることは人 \(i\) までを左に寄せた状態ではありえないからです。

結局indexについてはその総和が知りたいです。 \(inv\) についてはBITなどを用いることで \(i\) の降順に求まります。indexの総和については \(i\) の昇順に求めることができます。 \(i=3\) から \(i=4\) についての差分は \(i=3\) の時点で人 \(4\) がどこにいるかと人 \(4\) が左に行く際に何人を右に寄せたか(すなわち身長が高い人で自分より左にいる人が何人いたか)が分かればよく、これもBITを使って求められます。