#include <iostream>
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> nextGreaterElements(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> result(n, -1); // Initialize result with -1
        std::stack<int> st; // Stack to keep track of indices

        // Iterate through the array twice to simulate circular behavior
        for (int i = 0; i < 2 * n; ++i) {
            while (!st.empty() && nums[st.top()] < nums[i % n]) {
                result[st.top()] = nums[i % n];
                st.pop();
            }
            if (i < n) {
                st.push(i);
            }
        }
        return result;
    }
};



void testNextGreaterElements() {
    Solution solution;

    // Test case 1
    std::vector<int> nums1 = {1, 2, 1};
    std::vector<int> result1 = solution.nextGreaterElements(nums1);
    std::vector<int> expected1 = {2, -1, 2};
    std::cout << "Test 1 " << (result1 == expected1 ? "passed" : "failed") << std::endl;

    // Test case 2
    std::vector<int> nums2 = {1, 2, 3, 4, 3};
    std::vector<int> result2 = solution.nextGreaterElements(nums2);
    std::vector<int> expected2 = {2, 3, 4, -1, 4};
    std::cout << "Test 2 " << (result2 == expected2 ? "passed" : "failed") << std::endl;

    // Additional Test case 3
    std::vector<int> nums3 = {5, 4, 3, 2, 1};
    std::vector<int> result3 = solution.nextGreaterElements(nums3);
    std::vector<int> expected3 = {-1, 5, 5, 5, 5};
    std::cout << "Test 3 " << (result3 == expected3 ? "passed" : "failed") << std::endl;

    // Additional Test case 4
    std::vector<int> nums4 = {8, 7, 9, 5, 6};
    std::vector<int> result4 = solution.nextGreaterElements(nums4);
    std::vector<int> expected4 = {9, 9, -1, 6, 8};
    std::cout << "Test 4 " << (result4 == expected4 ? "passed" : "failed") << std::endl;

    // Additional Test case 5 (single element)
    std::vector<int> nums5 = {10};
    std::vector<int> result5 = solution.nextGreaterElements(nums5);
    std::vector<int> expected5 = {-1};
    std::cout << "Test 5 " << (result5 == expected5 ? "passed" : "failed") << std::endl;
}

int main() {
    testNextGreaterElements();
    return 0;
}