#include <iostream>
#include <stack>
using namespace std;

void test()
{
	int Arr[] = {5,7,9,2,8,11,16,10,12};
	int Sol[9];

	stack<int> undecided;   // or a stack implemented using a linked list

	Sol[0] = -1;    // this is a given

	for(int i = 9 - 1; i != 0; --i) {
	    undecided.push(i); // we haven't found a smaller value for this Arr[i] item yet
	                       // note that all the items already on the stack (if any)
	                       // are smaller than the value of Arr[i] or they would have
	                       // been popped off in a previous iteration of the loop
	                       // below
	
	    while (!undecided.empty() && (Arr[i-1] < Arr[undecided.top()])) {
	        // the value for the item on the undecided stack is
	        //  larger than Arr[i-1], so that's the index for 
	        //  the item on the undecided stack
	        Sol[undecided.top()] = i-1;
	        undecided.pop();
	    }
	}

	// We've filled in Sol[] for all the items have lesser values to
	//  the left of them.  Whatever is still on the undecided stack
	//  needs to be set to -1 in Sol
	
	while (!undecided.empty()) {
	    Sol[undecided.top()] = -1;
	    undecided.pop();
	}
	
	for (int i = 0; i < 9; ++i) {
		cout << Sol[i] << ", ";
	}
	
	cout << "\n";
}


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