/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	  public static void main(String[] args)
  {
    int arr[] =
    {
      40, 30, 35, 60, 80, 100
    };
    System.out.println(isValid(arr, 0, arr.length, Integer.MIN_VALUE, Integer.MAX_VALUE));
  }
 
  public static boolean isValid(int arr[], int start, int end, int min, int max)
  {
    if (end < start || start >= arr.length)
      return true;
    int root = arr[start];
    if (root < min || root > max)
      return false;
    int i = start + 1;
    for (i = start + 1; i < end; i++)
    {
      if (arr[i] < min || arr[i] > max)
        return false;
      if (root < arr[i])
        break;
    }
    return isValid(arr, start + 1, i - 1, min, arr[start]) && isValid(arr, i, end, arr[start], max);
  }
 
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCSAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykKICB7CiAgICBpbnQgYXJyW10gPQogICAgewogICAgICA0MCwgMzAsIDM1LCA2MCwgODAsIDEwMAogICAgfTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbihpc1ZhbGlkKGFyciwgMCwgYXJyLmxlbmd0aCwgSW50ZWdlci5NSU5fVkFMVUUsIEludGVnZXIuTUFYX1ZBTFVFKSk7CiAgfQoKICBwdWJsaWMgc3RhdGljIGJvb2xlYW4gaXNWYWxpZChpbnQgYXJyW10sIGludCBzdGFydCwgaW50IGVuZCwgaW50IG1pbiwgaW50IG1heCkKICB7CiAgICBpZiAoZW5kIDwgc3RhcnQgfHwgc3RhcnQgPj0gYXJyLmxlbmd0aCkKICAgICAgcmV0dXJuIHRydWU7CiAgICBpbnQgcm9vdCA9IGFycltzdGFydF07CiAgICBpZiAocm9vdCA8IG1pbiB8fCByb290ID4gbWF4KQogICAgICByZXR1cm4gZmFsc2U7CiAgICBpbnQgaSA9IHN0YXJ0ICsgMTsKICAgIGZvciAoaSA9IHN0YXJ0ICsgMTsgaSA8IGVuZDsgaSsrKQogICAgewogICAgICBpZiAoYXJyW2ldIDwgbWluIHx8IGFycltpXSA+IG1heCkKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgIGlmIChyb290IDwgYXJyW2ldKQogICAgICAgIGJyZWFrOwogICAgfQogICAgcmV0dXJuIGlzVmFsaWQoYXJyLCBzdGFydCArIDEsIGkgLSAxLCBtaW4sIGFycltzdGFydF0pICYmIGlzVmFsaWQoYXJyLCBpLCBlbmQsIGFycltzdGFydF0sIG1heCk7CiAgfQoKfQ==