###
Check if a given array can represent Preorder Traversal of Binary Search Tree. OR

Check if given Preorder traversal is valid BST (Binary Search Tree). OR

Given an array of numbers, verify whether it is the correct Preorder traversal sequence of a binary search tree.

You are given an array of numbers which represents Preorder traversal of Binary Search Tree.

Verify whether it is a correct Preorder sequence or not.

**Lets understand what is the input and the expected output.**

Input: [40, 30, 35, 20, 80, 100] Output: Invalid Preorder traversal

Input: [45, 25, 15, 35, 75]

Output: Valid Preorder traversal

Input: [50, 39, 44, 28, 85]

Output: Invalid Preorder traversal

Input: [10, 25, 5]

Output: Invalid Preorder traversal

Input: [30, 20, 10, 40, 50]

Output: Valid Preorder traversal