Selling shoes of the right size
Repetition

Except the additional list these lines are identical: 

shoes = map(int, input().strip().split())

query = list(map(int, input().split()))


You can write a function:

def read_integers_from_line(line):
    """
    &gt;&gt;&gt; list(read_integers_from_line("12 3 7"))
    [12, 3, 7]
    """
    return map(int, line.strip().split())


That you can use twice.

Tuple unpacking

Instead of query = read_integers_from_line(input()) you can use: shoe, price = read_integers_from_line(input()) so that the code becomes more self-descriptive.

Skipping the first line

The first line contains useless information, you skip it weirdly using a range but I would suggest a more explicit skip by using instead _ = input()