The question can be boiled down into this: Find the biggest element less than or equal to ~q_i~. This can be done a number of ways.

One solution is to sort the array then binary search it for every query. If the element, ~q_i~ was found, that is the turkey that must be bought. If it does not exist, the turkey that must be bought is the element directly preceding where the value ~q_i~ would go in the arrays. This is sufficient to pass the first subtask.
Pseudocode:

int[] values <- input
sort(values)
for every query:
  int q_i <- input
  index <- binarySearch(values, q_i)
  print(index)

Time Complexity: qlog(n)

Another approach is to construct an array, ~a~, that can be used to look up the result for every value of ~q_i~ such that ~a_{q_i}~ is the answer for ~q_i~. This allows for O(1) queries. For every value ~n_i~, set ~a_{n_i}~ to ~n_i~ then set the value of indices ~[n_i, n_{i+1})~ in ~a~ to ~n_i~.
Pseudocode:

int[1000001] answers
int[] values <- input
for i = 0 to length(values):
  answers[values[i]] <- values[i]
int answer <- answers[1]
for i = 2 to length(answers):
  if answers[i] == 0:
    answers[i] = answer
  else
    answer = answers[i]
for every query:
  int q_i <- input
  print(answers[q_i])