Next Greater Element I

Given two arrays nums1 (a subset of nums2, all values distinct) and nums2, for each value in nums1 find its next greater element to the right in nums2 — or -1 if none exists.

Example

Input: nums1 = 4 1 2, nums2 = 1 3 4 2 Output: -1 3 -1

Approach

Scan nums2 once with a monotonic decreasing stack of values. Whenever the current value beats the stack's top, that top value's "next greater" has just been found — pop it and record the mapping, repeat while the top still loses, then push the current value. After one O(n) pass over nums2, look up each nums1 value in the resulting map (default -1).

Input format

Line 1: nums1, space-separated Line 2: nums2, space-separated

Print the result, space-separated.