Given n number each representing value of a node, construct a tree in the following manner:
- Let's say node to be inserted has value x
- If x is less than or equal to value of the current root node then insert to the left of the current root
- If x is greater than the value of the current root then insert node in the right of this node
The above insertion will make a special tree known as Binary Search Tree. Determine whether the tree is balanced or not. A tree is said to be balanced if the absolute difference between the depth of left subtree and the right subtree of each node does not differ by more than 1.
Input Format:
First line of input contains an integer t i.e. number of test cases. In the next t lines first line contains an integer n denoting number of nodes in the tree followed by n space separated integers.
Output Format:
For each test case print "Yes" if the tree is balanced else print "No".
Constraints:
1 <= t <= 20
All other integers are well with in the integer range.
For case 1 constructed tree is:
2
/ \
1 3
Here node 1 and 3 are already balanced. For node 2 depth of left subtree and right subtree is 1 (if depth of root is considered to be 0) and difference between them is 0, since for all the nodes this different is zero hence the tree is balanced.
For case 2 constructed tree is:
3
/
2
/
1
Here different between the depth of the left subtree and right subtree is 2 hence the tree is unbalanced.
