Phần tử lớn hơn tiếp theo I (Next Greater Element I)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai mảng số nguyên khác nhau từng đôi nums1 và nums2, trong đó mọi phần tử của nums1 đều xuất hiện trong nums2. Với mỗi giá trị $x$ của nums1, xét vị trí của $x$ trong nums2 và tìm phần tử đầu tiên ở bên phải có giá trị lớn hơn $x$. Nếu không có, kết quả là $-1$.

Input

Dòng đầu chứa $m$ và $n$, là độ dài nums1 và nums2. Dòng thứ hai chứa $m$ phần tử của nums1. Dòng thứ ba chứa $n$ phần tử của nums2.

Output

In $m$ số nguyên theo thứ tự của nums1, mỗi số là phần tử lớn hơn tiếp theo tương ứng trong nums2, hoặc $-1$.

Subtask

• Subtask 1 (30 điểm): Các điều kiện gốc và nums2 tăng nghiêm ngặt.
• Subtask 2 (70 điểm): $1\le m\le n\le1000$, $0\le nums1_i,nums2_i\le10^4$; mỗi mảng không có phần tử lặp và nums1 là tập con của nums2.

Ví dụ

Input

3 4
4 1 2
1 3 4 2

Output

-1 3 -1

Giải thích

Ta có nums1 = [4,1,2] và nums2 = [1,3,4,2].

• Giá trị $4$ nằm ở vị trí thứ $3$ của nums2. Bên phải chỉ còn $2<4$, nên không có phần tử lớn hơn tiếp theo: kết quả là $-1$.
• Giá trị $1$ nằm ở vị trí đầu của nums2. Phần tử ngay bên phải là $3>1$, nên kết quả là $3$.
• Giá trị $2$ nằm ở vị trí cuối của nums2, nên không có phần tử nào ở bên phải: kết quả là $-1$.

Theo thứ tự của nums1, chương trình in -1 3 -1.