import java.util.*;
class Main{
static boolean preorderBST(int input[], int n)
{
Stack<Integer> s = new Stack<Integer>();
for(int i=0;i<n;i++)
{
// if current node is smaller than the root
// the current node lies on the right of root
// thus it is impossible for bst
if (input[i] < root)
return false;
// keep removing elements smaller than the root
// until you find an element which is greater than the root
while(!s.empty() && s.peek()<input[i]){
root = s.peek();
s.pop();
}
// if current element is smaller than the root
// push it into stack
s.push(input[i]);
}
// if we passed until the end of the array
// that means that the given preorder sequence represents a valid BST
return true;
}
public static void main
(String[] args
) {
int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
int n = input.length;
System.
out.
print((preorderBST
(input, n
)) ? "yes" : "no"); }
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgTWFpbnsKCXN0YXRpYyBib29sZWFuIHByZW9yZGVyQlNUKGludCBpbnB1dFtdLCBpbnQgbikKCXsKCSAgICBTdGFjazxJbnRlZ2VyPiBzID0gbmV3IFN0YWNrPEludGVnZXI+KCk7CgkgICAgaW50IHJvb3QgPSBJbnRlZ2VyLk1JTl9WQUxVRTsKCSAgICBmb3IoaW50IGk9MDtpPG47aSsrKQoJICAgIHsKCSAgICAgICAgLy8gaWYgY3VycmVudCBub2RlIGlzIHNtYWxsZXIgdGhhbiB0aGUgcm9vdAoJICAgICAgICAvLyB0aGUgY3VycmVudCBub2RlIGxpZXMgb24gdGhlIHJpZ2h0IG9mIHJvb3QKCSAgICAgICAgLy8gdGh1cyBpdCBpcyBpbXBvc3NpYmxlIGZvciBic3QKCSAgICAgICAgaWYgKGlucHV0W2ldIDwgcm9vdCkKCSAgICAgICAgICAgIHJldHVybiBmYWxzZTsKCSAgICAgICAgLy8ga2VlcCByZW1vdmluZyBlbGVtZW50cyBzbWFsbGVyIHRoYW4gdGhlIHJvb3QKCSAgICAgICAgLy8gdW50aWwgeW91IGZpbmQgYW4gZWxlbWVudCB3aGljaCBpcyBncmVhdGVyIHRoYW4gdGhlIHJvb3QKCSAgICAgICAgd2hpbGUoIXMuZW1wdHkoKSAmJiBzLnBlZWsoKTxpbnB1dFtpXSl7CgkgICAgICAgICAgICByb290ID0gcy5wZWVrKCk7CgkgICAgICAgICAgICBzLnBvcCgpOwoJICAgICAgICB9CgkgICAgICAgIC8vIGlmIGN1cnJlbnQgZWxlbWVudCBpcyBzbWFsbGVyIHRoYW4gdGhlIHJvb3QKCSAgICAgICAgLy8gcHVzaCBpdCBpbnRvIHN0YWNrCgkgICAgICAgIHMucHVzaChpbnB1dFtpXSk7CgkgICAgfQoJICAgIC8vIGlmIHdlIHBhc3NlZCB1bnRpbCB0aGUgZW5kIG9mIHRoZSBhcnJheQoJICAgIC8vIHRoYXQgbWVhbnMgdGhhdCB0aGUgZ2l2ZW4gcHJlb3JkZXIgc2VxdWVuY2UgcmVwcmVzZW50cyBhIHZhbGlkIEJTVAoJICAgIHJldHVybiB0cnVlOwoJfQoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpCgl7CgkgICAgaW50IGlucHV0W10gPSB7NSwgMywgNCwgNywgNiwgOSwgOCwgMTF9OwoJICAgIGludCBuID0gaW5wdXQubGVuZ3RoOwoKCSAgICBTeXN0ZW0ub3V0LnByaW50KChwcmVvcmRlckJTVChpbnB1dCwgbikpID8gInllcyIgOiAibm8iKTsKCX0KfQ==