Next Greater Element I

For a value x in array b, its next greater element is the first value to the right of x in b that is larger than x (or -1 if there is none). Array a is a subset of b; for every value of a, print its next greater element in b.

Input:

• line 1: n1 n2
• line 2: the n1 values of a
• line 3: the n2 values of b (all distinct)

Output: n1 numbers on one line.

Constraints: 1 ≤ n1 ≤ n2 ≤ 10⁵, 0 ≤ value ≤ 10⁵; every value of a appears in b.

Think about it: a monotonic stack answers "next greater" for every element of b in one O(n) pass — store the answers in a hash map, then look up each value of a.