17762번 - Building 2 다국어

문제

日本には N 個の街があり,それらの間は N − 1 本の双方向に通行可能な道路で結ばれている.どの街か らどの街へもいくつかの道路をたどって行くことができる.各街には役所のビル 1 つがあり,街 i のビル の高さを H_i とする.

国際情報オリンピックが日本で開かれるに伴い,世界の選手達を歓迎するため,観光ツアーを計画しよ うとしている.観光ツアーは,ある街からスタートし,道路をたどって違う街へ移動することを繰り返し, ある街で終了する.この時,同じ街を 2 度以上訪れることはないようにすることとなっている.

世界の選手たちをより一層歓迎するため,観光で訪れるうちの一部の街の役所のビルを飾り付けること にした.ある著名なデザイナーにデザインを依頼したところ,飾りつけに利用するビルは,出発する街か ら到着する街に向けて高くなっていく必要があると言った.つまり,役所のビルを飾り付けることにした 街を i₁, i₂,..., i_k とおき,観光ツアー中にこれらの街を i₁, i₂,..., i_k という順番で訪れるとしたとき,ビルの 高さが H_i1 < H_i2 < ··· < H_ik となっていなければならない.(全ての訪れる街のビルを飾り付けなければな らないわけではないことに注意せよ.)

できるだけ飾りつけを華やかにするため,飾りつけに利用するビルの数をできるだけ多くしたい.開始 する街,終了する街,ビルの飾り付けをする街を自由に選べるとしたとき,飾りつけに利用することので きるビルの数の最大値を計算するプログラムを作れ.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 N が書かれており,街の数を表す.
• 続く N 行には,各街の役所のビルの高さに関する情報が与えられる.これらの行のうちの i 行目に は整数 H_i が書かれている.これは街 i のビルの高さが Hi であることを表す.
• 続く N − 1 行には,道路に関する情報が与えられる.これらの行のうちの i 行目には整数 A_i, B_i (1 ≤ A_i < B_i ≤ N) が空白を区切りとして書かれている.これは i 番目の道路が街 A_i と街 B_i を結んで いることを表す.

출력

標準出力に,飾りつけに利用することのできるビルの数の最大値を表す整数を出力せよ.

제한

• 2 ≤ N ≤ 100 000 街の数
• 1 ≤ H_i ≤ 1 000 000 000 街 i のビルの高さ

힌트