なら自分も広義単調増加で
LISだし二分探索のO(NlogN)で実装
https://ideone.com/kN5UFU