You are given an integer array order representing the insertion order of elements into an initially empty Binary Search Tree (BST).

Return the maximum depth of the resulting BST after inserting all elements in order without performing any rebalancing operations.

The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Constraints:

• n $==$ order.length

• $1 \leq$ n $\leq 10^5$

• order is a permutation of integers from $1$ to n.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.