import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone{
int[] arr = {6,3,1,8,2,9,7};
Stack<Integer> st1 = new Stack<Integer>();
Stack<Integer> st2 = new Stack<Integer>();
List<Integer> result = new ArrayList<>();
for(int i=arr.length-1;i>=0;--i){
while(!st1.isEmpty() && arr[(int)st1.peek()] < arr[i]){
st2.push(st1.pop());
}
if(st2.isEmpty()) result.add(-1);
else result.add(arr[(int)st2.peek()]);
while(!st2.isEmpty()) st1.push(st2.pop());
if(st1.isEmpty() || arr[(int)st1.peek()] > arr[i]){
st1.push(i);
}
}
System.
out.
println(result.
toString()); }
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmNsYXNzIElkZW9uZXsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbnsKCQlpbnRbXSBhcnIgPSB7NiwzLDEsOCwyLDksN307CgkJU3RhY2s8SW50ZWdlcj4gc3QxID0gbmV3IFN0YWNrPEludGVnZXI+KCk7CgkJU3RhY2s8SW50ZWdlcj4gc3QyID0gbmV3IFN0YWNrPEludGVnZXI+KCk7CgkJTGlzdDxJbnRlZ2VyPiByZXN1bHQgPSBuZXcgQXJyYXlMaXN0PD4oKTsKCQkKCQlmb3IoaW50IGk9YXJyLmxlbmd0aC0xO2k+PTA7LS1pKXsKCQkgICAgd2hpbGUoIXN0MS5pc0VtcHR5KCkgJiYgYXJyWyhpbnQpc3QxLnBlZWsoKV0gPCBhcnJbaV0pewoJCSAgICAJc3QyLnB1c2goc3QxLnBvcCgpKTsKCQkgICAgfQoJCSAgICAKCQkJaWYoc3QyLmlzRW1wdHkoKSkgcmVzdWx0LmFkZCgtMSk7CgkJCWVsc2UgcmVzdWx0LmFkZChhcnJbKGludClzdDIucGVlaygpXSk7CgkJCQoJCQl3aGlsZSghc3QyLmlzRW1wdHkoKSkgc3QxLnB1c2goc3QyLnBvcCgpKTsKCQkJCgkJCWlmKHN0MS5pc0VtcHR5KCkgfHwgYXJyWyhpbnQpc3QxLnBlZWsoKV0gPiBhcnJbaV0pewoJCQkJc3QxLnB1c2goaSk7CgkJCX0KCQl9CgkJCgkJQ29sbGVjdGlvbnMucmV2ZXJzZShyZXN1bHQpOwoJCVN5c3RlbS5vdXQucHJpbnRsbihBcnJheXMudG9TdHJpbmcoYXJyKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKHJlc3VsdC50b1N0cmluZygpKTsKCX0KfQ==
[6, 3, 1, 8, 2, 9, 7]
[2, 2, -1, 7, -1, 7, -1]