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

Nguồn: LeetCode

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

Đề bài

Cho một mảng được xem là vòng tròn: sau phần tử cuối lại quay về phần tử đầu. Với mỗi vị trí, hãy tìm giá trị lớn hơn đầu tiên gặp được khi đi sang phải theo vòng tròn. Không được dùng chính phần tử đó làm đáp án. Nếu không tồn tại, in $-1$.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên của mảng.

Output

In $n$ số nguyên là phần tử lớn hơn tiếp theo theo vòng tròn của từng vị trí, hoặc $-1$.

Subtask

• Subtask 1 (30 điểm): $n\le200$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le n\le10^4$, $-10^9\le nums_i\le10^9$.

Ví dụ

Input

3
1 2 1

Output

2 -1 2

Giải thích

Mảng vòng tròn là $[1,2,1]$.

• Với phần tử $1$ ở vị trí $1$, đi sang phải gặp ngay $2>1$, nên đáp án là $2$.
• Với phần tử $2$ ở vị trí $2$, đi qua phần tử $1$ ở vị trí $3$, sau đó vòng về vị trí $1$ có giá trị $1$; không giá trị nào lớn hơn $2$, nên đáp án là $-1$.
• Với phần tử $1$ ở vị trí $3$, sau khi vòng về đầu mảng ta gặp $1$ ở vị trí $1$ bằng nó nên chưa đủ; tiếp theo gặp $2>1$ ở vị trí $2$, nên đáp án là $2$.

Do đó output là 2 -1 2.