AIOC Banner

Problem: Bookshop

Want to try solving this problem? You can submit your code online if you log in or register.


Time Limit: 1 second
Memory Limit: 16 Mb

You are the author of a once world-famous book series with a plot revolving around wizards, flying broomsticks and disgruntled dark lords. In their prime you sold millions of books. At one point, every self-respecting teenager had the complete series. The secret of your success, never revealed to anyone, is that each book you released had a strictly greater width, measured in number of pages, than your previous book. Sadly, as time has passed on, you have slowly faded to obscurity, your once-famous books all but forgotten.

On one particularly dull day you find yourself in an antique book store. The store has a single long shelf filled with countless books, all of different widths. The books on the shelf are kept sorted in chronological order, with the oldest books at the left-hand side of the shelf and the newest books at the right-hand side.

In a fit of nostalgia, you decide to find the copies of your once-famous books on the shelf. So much dust has accumulated on the books that it is impossible to make out the titles by trying to read their spines. Fortunately, all the books on the shelf have different widths, and you happen to remember the precise width of each of the books you have published, allowing you to hunt for them.

Your task is to find the location of each of your books on the bookshelf. You are given the list of the widths of each of the N books on the bookshelf, ordered from the oldest book to the newest book. Additionally, you are given a list of the widths of each of the K books you have published, also ordered from oldest to newest. No two books on the shelf have the same width, and you are certain that the shelf contains one copy of each of your books.



Your program must read from standard input. The first line of input will contain a single integer N, the number of books on the bookshelf. The following N lines will each contain a single integer Ai, describing the width of one book on the bookshelf. These books will be listed in chronological order (from left to right). No two books will have the same width.

The following line will contain a single integer K, the number of books that you have published. The following K lines will each contain a single integer Bj, describing the width of the jth book that you wish to find. Your books will be listed in chronological order (so the widths B1,...,BK will appear in sorted order in the list A1,...,AN), and each book's width will be strictly greater than the previous (so B1 < B2 < ...< BK).


Your program must write K lines to standard output. The jth line of the output should contain a single integer describing the position on the bookcase of the jth book you have written. The first book on the bookcase has position 1, while the last book on the bookcase has position N.

Sample Input


Sample Output



In this example, you are standing in front of a bookshelf containing 9 books. Furthermore, you have published 5 books that you wish to find on the bookshelf. The first book you wish to find has width 223 and appears as the second book on the bookshelf, which means that the first location that you output is 2. Similarly, your remaining books of widths 251, 317, 636, and 766 appear in locations 3, 5, 7 and 8 on the store bookshelf respectively.


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 25 March 2023,  7:31pm AEDT