Заправки

У країні є $n$ міст, деякі з яких з'єднані між собою дорогами. Для того щоб проїхати по одній дорозі, потрібно один бак бензину. У кожному місті вартість повного бака бензину різна. Ваше завдання — дістатися з першого міста до $n$-го з мінімальними витратами.

Вхідні дані

Перший рядок містить кількість міст $n(1\le n\le 100)$. Другий рядок містить $n$ чисел, де $i$-те число задає вартість бензину в $i$-му місті (всі числа цілі, від $0$ до $100$). Третій рядок містить кількість доріг $m$ у країні, після чого наводиться опис самих доріг. Кожна дорога задається двома числами — номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто по них можна рухатися в обох напрямках), між двома містами існує не більше однієї дороги, а також немає доріг, що ведуть з міста в себе.

Вихідні дані

Виведіть одне число — мінімальну вартість маршруту або $-1$, якщо дістатися до $n$-го міста неможливо.

Приклади