gogo40 contest (2015/01)

Độ xấu của 1 dãy số có n phần tử được định nghĩa là tổng của same(a[i], a[i + 1]), i chạy từ 1 -> n - 1 với same(x, y) trả về 1 nếu x = y, trả về 0 nếu x <> y.

Từ một dãy số ban đầu, bạn có thể thực hiện các dạng biến đổi với số lần tùy ý (một dạng có thể dùng nhiều lần hoặc không dùng lần nào). Dạng biến đổi thứ i có thể biến một số bất kỳ trong dãy có giá trị x[i] thành y[i] hoặc từ y[i] thành x[i].

Nhiệm vụ của bạn là sử dụng các biến đổi trên để biến dãy thành một dãy xấu nhất có thể.

Input

• Dòng 1: Số nguyên dương n (n <= 10⁵, 50% số test có n <= 10³)
• Dòng 2: Gồm n số mô tả dãy ban đầu (0 <= a[i] <= n)
• Dòng 3: Số nguyên dương m là số cách biến đổi (m <= 10⁵)
• m dòng tiếp theo, mỗi dòng gồm 2 số nguyên x[i], y[i] mô tả cách biến đổi thứ i

Output

• Gồm 1 số nguyên duy nhất là độ xấu lớn nhất của dãy sau khi biến đổi

Example

Input:
5
1 2 3 2 1
3
1 2
3 4
2 5
Output:
2
(Giải thích: biến đổi dãy về 5 5 4 5 5 để tạo ra được dãy có độ xấu lớn nhất là 2)