Count Valid Sets of Creatures

In this problem, you are given a group of creatures where each creature brings a gem of a certain type. The creatures also have a hierarchical relationship given as a list of ordered pairs (A, B), which means creature A is the direct superior of creature B. A set of creatures is said to be valid if the gem types of the creatures in the set, when sorted, form a contiguous sequence. In other words, if (p = \min(S)) and (q = \max(S)), then the set is valid if its gems are exactly ({p, p+1, \ldots, q}).

Your task is to count the number of distinct valid sets of creatures that can be obtained by exploring the hierarchy starting from any creature. Note that even a single creature forms a valid set (since a single number is trivially contiguous). The hierarchy is represented as a directed tree, and you are allowed to extend a set by moving from a creature to any of its direct subordinates.

For clarity, suppose you have a set (S) of creatures and let (g(i)) be the gem type of creature (i). Let [ L = { g(i) : i \in S }] Then the set (S) is valid if and only if [ \text{sorted}(L) = [\min(L), \min(L)+1, \ldots, \max(L)] ]

Your solution should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer (n) representing the number of creatures.
2. The second line contains (n) space-separated integers where the (i)-th integer represents the gem type of the (i)-th creature.
3. The third line contains a single integer (m) representing the number of hierarchy relationships.
4. The next (m) lines each contain two space-separated integers (A) and (B), indicating that creature (A) is the direct superior of creature (B).

outputFormat

Output a single integer representing the number of distinct valid sets of creatures found by exploring the hierarchy.## sample

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

7