Chefina on a Trip

As we all know, Chefland consists of $N$ cities (numbered $1$ through $N$) connected by $N-1$ roads in such a way that each city is reachable from all other cities. In other words, the cities and roads form a tree. For each valid $i$, the $i$-th city's height above sea level is $A_i$. A path between two cities is said to be *beautiful* if the heights of the cities in the path first increase and