Uzastopni

Ο Petar κάνει πάρτι γενεθλίων και αποφάσισε να καλέσει κάποιους από τους υπαλλήλους της εταιρείας του όπου είναι διευθύνων σύμβουλος.
Κάθε υπάλληλος, συμπεριλαμβανομένου του Petar, έχει μια μοναδική ετικέτα από το 1 έως το ~N~ και ένα συνοδευτικό είδος αστείων που λένε ~V_i~ . Επίσης, κάθε υπάλληλος της εταιρείας εκτός από τον Petar έχει ακριβώς έναν προϊστάμενο.
Δεδομένου ότι ο Petar είναι ο Διευθύνων Σύμβουλος της εταιρείας, έχει την ετικέτα 1 και είναι άμεσα ή έμμεσα ανώτερος όλων των εργαζομένων.
Στο πάρτι γενεθλίων, υπάρχουν ορισμένοι κανόνες που πρέπει να ακολουθούν όλοι οι παρευρισκόμενοι (συμπεριλαμβανομένου του Petar).

• Στο πάρτι, δεν πρέπει να υπάρχουν δύο άτομα που λένε τα ίδια αστεία.
• Το άτομο ~X~ δεν μπορεί να προσκληθεί εάν δεν προσκληθεί ο άμεσος προϊστάμενός του.
• Το άτομο ~X~ δεν μπορεί να προσκληθεί εάν το σύνολο των ανέκδοτων που λένε οι προσκεκλημένοι στους οποίους αυτός είναι ανώτερος(άμεσα ή έμμεσα) και το άτομο ~X~ δεν σχηματίζει ένα σύνολο διαδοχικών αριθμών.

Οι αριθμοί στο σύνολο είναι διαδοχικοί εάν η διαφορά μεταξύ γειτονικών στοιχείων είναι ακριβώς 1 όταν το σύνολο ταξινομείται με αύξοντα τρόπο. Για παράδειγμα, ~(3,\;1,\;2)~ και ~(5,\;1,\;2,\;4,\;3)~.
Ο Petar θέλει να μάθει πόσα διαφορετικά σετ αστείων μπορεί να δει στο πάρτι του με τους αναφερόμενους περιορισμούς.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N,\;(1 \leq N \leq 10\,000)~.
Η δεύτερη γραμμή εισόοδυ περιέχει ~N~ ακέραιους αριθμούς, τους τύπους ανέκδοτων που λέει το άτομο ~i~, ~V_i,\;(1 \leq V_i \leq 100)~. Κάθε μία από τις ακόλουθες ~N-1~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A~ και ~B~, ~(1 \leq A, B \leq N)~, που δηλώνουν ότι το άτομο ~A~ είναι άμεσα ανώτερο από το άτομο ~B~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον αριθμό των διαφορετικών σετ αστείων που συμμορφώνονται με τους περιορισμούς που αναφέρονται προηγουμένως.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα ισχύει ότι το ~N~ δεν υπερβαίνει το 100.

Παραδείγματα

input

4
2 1 3 4
1 2
1 3
3 4

output

6

Επεξήγηση του 1ου παραδείγματος:

Είναι δυνατό να έχετε τα ακόλουθα σετ αστείων στο πάρτι: ~\{2\},\;\{2,\;3\},\;\{2,\;3,\;4\},\;\{1,\;2,\;3,\;4\},\;\{1,\;2\},\;\{1,\;2,\;3\}~.

input

4
3 4 5 6
1 2
1 3
2 4

output

3

Επεξήγηση του 2ου παραδείγματος:

Τα μόνα πιθανά σύνολα αστείων είναι: ~\{3\},\;\{3,\;4\},\;\{3,\;4,\;5\}~. Παρατηρήστε ότι το άτομο που λέει το αστείο 6 δεν μπορεί να είναι στο πάρτι επειδή, σε αυτήν την περίπτωση, το σύνολο των ανέκδοτων ~\{4,\;6\}~ δεν είναι ένα σύνολο διαδοχικών αριθμών.

input

6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6

output

10