\(i\) 番目の人をリーダーにしたときに振り向かなければならない人数は, 区間 \([1,i-1]\) で西を向いている人数と区間 \([i+1,N]\) で東を向いている人数の和である. これは西を向いている人数の累積和を計算しておけば \(O(1)\) で計算できる.

後はすべての人をリーダーにしたときの振り向かなければならない人数を計算して最小値を取る.