#include <cstdio>

template <class T, class K> T BS( T L, T R, K x )
{
  while (L + 1 != R)
  {
    T M = L + (R - L) / 2;
    if (*M <= x)
      L = M;
    else
      R = M;
  }
  return L;
}

int main()
{
  int x[] = {1, 2, 3, 3, 5, 5, 6, 7, 8};
  int xlen = sizeof(x) / sizeof(x[0]);
  int y[] = {3, 4, 5, 6};
  int ylen = sizeof(y) / sizeof(y[0]);

  for (int i = 0; i < ylen; i++)
    printf("%d : %d\n", y[i], *BS(x, x + xlen, y[i]));
  return 0;
}