upper_bound の結果から -1 すれば取れるというのは見当がついているが、問題はこれが 1F 中に数十回呼ばれる可能性があり haystack の分布がかなり偏りそう(8 割は数要素だがまれに 3 桁ぐらいある)みたいな