Diameter of Binary Tree

Mediumjavapythonccppjavascript

Find the diameter of a binary tree: the number of edges on the longest path between any two nodes (the path need not pass through the root).

Input Format

The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null).

Output Format

Print the diameter, measured in edges.

Example 1

Input

5
1 2 3 4 5

Output

Explanation: One longest path is 4 -> 2 -> 1 -> 3, containing three edges.

Run your code to see output here...