514. Coding Test

0

Easy

Coding Blocks conducted a coding test for students to grab scholarships. The question was to find the next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays arr1 and arr2, where arr1 is a subset of arr2. For each 0 <= i < arr1.length, find the index j such that arr1[i] == arr2[j] and determine the next greater element of arr2[j] in arr2. If there is no next greater element, then the answer for this query is -1.

Input Format

First Line contains size of arr1, second line contains elements of arr1, Third line contains size of arr2, Fourth line contains elements of arr2

Output Format

Print ans array which has size same as arr1 such that ans[i] is next greater element.

Example

Input

3 4 1 2 4 1 3 4 2

Output

-1 3 -1

Constraints

1 <= arr1.length <= arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 104
All integers in arr1 and arr2 are unique.
All the integers of arr1 also appear in arr2.