逆に辿る方が簡単？
for any k＜n,
最後のk+1区間（n-k〜n）が右向き、区間n-k-1が左向きとすると
最後のk区間（n-k+1 〜 n）が支配区間で、初めのn-k区間（1〜n-k）は支配区間でない。
（区間n-k-1 と区間n-kは重ならない。）
>>687
区間j-1 と区間j が同じ向き ⇔ A(j)，B(j）が反対側
区間j-1 と区間j が逆向き ⇔ A(j)，B(j）が同じ側
なので、
最後のk+1区間（n-k〜n）が同じ向き ⇔ 最後のk区間（n-k+1 〜n）でA(j）とB(j）が反対側
（区間nが右向きということを使えば、まだ改良できるけど…）
