This page is still under construction.

Parts of this page are still being built. What you see may change.

Auction Market

Interview

Time limit1sMemory limit512 MB

Summary
Buyers in fixed order scan items left to right and bid on the first item they can afford or outbid, and we count how many items end up with a bidder.
Level

Medium6 of 10

Topics
Greedy, Binary search, Segment tree, Implementation
Solved
No attempts yet

Problem

On a particular day, N items numbered from 1 to N are sold at an auction market, and the starting price of the ith item is Si. There are M potential buyers numbered from 1 to M who want to take part in the auction, and the budget of the jth potential buyer is Bj.

One by one, from the 1st potential buyer to the Mth potential buyer, each potential buyer inspects the items one by one from the 1st to the Nth and decides whether he is able to bid on that item. The jth potential buyer is able to bid on the ith item if and only if at least one of the following conditions holds.

  • No one has bid on the ith item yet and Bj ≥ Si.
  • Someone has bid on the ith item and Bj is strictly larger than the current highest bid for that ith item.

If the jth potential buyer is able to bid on the ith item, he bids Bj on that ith item and stops inspecting the remaining items, that is, he ignores the (i + 1)th to Nth items. With this behavior, each potential buyer bids on at most 1 item. A potential buyer may also fail to bid on any item at all, for example when his budget is too low.

At the end of the day, after all the potential buyers have either placed their bid or inspected all items, the highest bid for each item is determined and the items are sold to the respective highest bidders. Items with no bidder are not sold.

Find how many items are successfully sold at the end of the day.

Input

Input begins with a line containing an integer: N (1 ≤ N ≤ 100 000), the number of items to be sold at the auction market. The second line contains N integers: Si (1 ≤ Si ≤ 109), the starting price of each item. The third line contains an integer M (1 ≤ M ≤ 100 000), the number of potential buyers. The fourth line contains M integers: Bj (1 ≤ Bj ≤ 109), the budget of each potential buyer.

Output

Output in one line an integer, the number of items that are successfully sold at the end of the day.

Examples3

  1. Example 1

    Input
    3
    100 200 150
    5
    110 250 220 130 140
    
    Expected output
    2
    
  2. Example 2

    Input
    4
    1000 1000 1000 1000
    4
    3000 2000 2500 1000
    
    Expected output
    3
    
  3. Example 3

    Input
    5
    10 40 30 50 20
    4
    5 50 10 15
    
    Expected output
    1