SPOJ in Armenian

Տրված է n գագաթ պարունակող բինար ծառ, որտեղ 1 համարով գագաթը ծառի արմատն է։ Ծառի գագաթներից յուրաքանչյուրի վրա գրված է 1-ից n միջակայքի ինչ-որ թիվ, և ավելին` բոլոր գագաթներում գրված են տարբեր թվեր։

Բինար ծառի շրջանցման հաջորդականությունը կսահմանենք ռեկուրսիվ ձևով․

• Վերցնենք ծառի արմատի ձախ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե ձախ զավակը գոյություն չունի, կվերցնենք դատարկ հաջորդականություն)
• Վերցնենք ծառի արմատում գրված թիվը
• Վերցնենք ծառի արմատի աջ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե աջ զավակը գոյություն չունի կվերցնենք դատարկ հաջորդականություն)

Այսպիսով, բինար ծառի շրջանցման հաջորդականությունը կլինի վերը նշված 3 հաջորդականությունների կցումը միմյանց։

Ինչպես բոլորս գիտենք, բինար ծառում կամայական գագաթ ունի աջ և ձախ զավակ, բայց այս խնդրում ձեզ տրված է հնարավորություն ընտրելու, թե որ զավակն է ձախը, իսկ որը աջը։ Այսպիսով ձեր խնդիրն է, կամայական գագաթի համար այնպես որոշել աջ և ձախ զավակներին այնպես, որ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակը լինի հնարավորինս քիչ։
Հիշեցնենք, որ S հաջորդականության ինվերսիաների քանակը հավասար է այն (i, j) զույգերի քանակին, որտեղ 1 ≤ i < j ≤ size(S), իսկ Si > Sj:

Մուտքային տվյալներ

Առաջին տողում տրված է մեկ բնական թիվ՝ n (1 ≤ n ≤ 2000). բինար ծառի գագաթների քանակը։
Երկրորդ տողում տրված են իրարից մեկական բացակով բաժանված n բնական թվեր՝ a1, a2, ..., an (1 ≤ ai ≤ n). գագաթներում գրված թվերը (բոլոր թվերը իրարից տարբեր են)։
Հաջորդ n - 1 տողերից յուրաքանչյուրում տրված է երկու բնական թիվ՝ v և u ( 1 ≤ v ≠ u, ≤ n)․ բինար ծառի կողերը։

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակի հնարավոր մինիմալ արժեքը։

Օրինակ