Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
 
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:
Input: arr = [6,1,9]
Output: 2

Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

 
Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Graph traversal

Starter code: class Solution:
    def minJumps(self, arr: List[int]) -> int:
        

Solutions:
from collections import deque

class Solution:

	def minJumps(self, arr: list) -> int:
		if len(arr) == 1:
			return 0
		graph = {}
		for (i, n) in enumerate(arr):
			if n in graph:
				graph[n].append(i)
			else:
				graph[n] = [i]
		curs = [0]
		other = [len(arr) - 1]
		visited = {0}
		visited2 = {len(arr) - 1}
		step = 0
		while curs:
			if len(curs) > len(other):
				(curs, other) = (other, curs)
				(visited, visited2) = (visited2, visited)
			nex = []
			for node in curs:
				for child in graph[arr[node]]:
					if child in visited2:
						return step + 1
					if child not in visited:
						visited.add(child)
						nex.append(child)
				for child in [node - 1, node + 1]:
					if child in visited2:
						return step + 1
					if 0 <= child < len(arr) and child not in visited:
						visited.add(child)
						nex.append(child)
			curs = nex
			step += 1
		return -1


class Solution:

	def minJumps(self, arr):
		length = len(arr)
		if len(set(arr)) == length:
			return length - 1
		if arr[0] == arr[-1]:
			return 1
		_map = defaultdict(set)
		for (i, val) in enumerate(arr):
			_map[val].add(i)
		(res, seen, visit) = (0, {0}, set())
		(curs, other) = ({0}, {length - 1})
		while curs:
			res += 1
			thisLevel = set()
			for i in curs:
				if i - 1 > 0 and i - 1 not in seen:
					thisLevel.add(i - 1)
				if arr[i] in _map:
					thisLevel |= _map[arr[i]] - seen
					visit.add(arr[i])
					del _map[arr[i]]
				if i + 1 < length and i + 1 not in seen:
					thisLevel.add(i + 1)
			if thisLevel & other:
				return res
			curs = thisLevel
			if len(curs) > len(other):
				(curs, other) = (other, curs)
			else:
				seen |= thisLevel


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		connected = collections.defaultdict(list)
		_ = [connected[v].append(i) for (i, v) in enumerate(arr)]
		(queue, pos_visited) = ([0], set([0]))
		steps = 0
		while queue:
			next_steps = []
			for cur_pos in queue:
				if cur_pos == len(arr) - 1:
					return steps
				next_steps += [cur_pos - 1, cur_pos + 1] + connected[arr[cur_pos]]
				connected[arr[cur_pos]].clear()
			queue = []
			for _ in next_steps:
				if _ >= 0 and _ < len(arr) and (_ not in pos_visited):
					queue.append(_)
					pos_visited.add(_)
			steps += 1
		return steps


class Solution:

	def minJumps(self, arr):
		n = len(arr)
		if n == 1:
			return 0
		d = defaultdict(list)
		for (i, val) in enumerate(arr):
			d[val].append(i)
		visited = set([0])
		stack = deque([0])
		(k, jumps) = (len(stack), 1)
		while stack:
			i = stack.popleft()
			childs = [j for j in [i - 1, i + 1] if arr[j] != arr[i]] + [j for j in d.pop(arr[i], [])]
			childs = [j for j in childs if 0 <= j < n and j not in visited]
			for j in childs:
				if j == n - 1:
					return jumps
				visited.add(j)
				stack.append(j)
			k -= 1
			if not k:
				k = len(stack)
				jumps += 1
		return jumps


from collections import defaultdict

class Solution:

	def get_jump_indices(self, arr):
		jump_indices = defaultdict(set)
		for (i, val) in enumerate(arr):
			jump_indices[val].add(i)
		return jump_indices

	def minJumps(self, arr: List[int]) -> int:
		jump_indices = self.get_jump_indices(arr)
		next_indices = [len(arr) - 1]
		visited = set()
		visited.add(len(arr) - 1)
		jumps = 0
		while next_indices:
			reachable_indices_set = set()
			for index in next_indices:
				if index == 0:
					return jumps
				reachable_indices = jump_indices[arr[index]].copy()
				reachable_indices.remove(index)
				reachable_indices.add(index - 1)
				if index != len(arr) - 1:
					reachable_indices.add(index + 1)
				for reachable_index in reachable_indices:
					if reachable_index in visited:
						continue
					visited.add(reachable_index)
					reachable_indices_set.add(reachable_index)
			next_indices = list(reachable_indices_set)
			jumps += 1
		return None


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		v2n = collections.defaultdict(set)
		for (i, v) in enumerate(arr):
			if 0 < i < len(arr) - 1 and arr[i - 1] == v and (arr[i + 1] == v):
				continue
			v2n[v].add(i)
		(visited, seen, q, step) = (set([0]), set(), collections.deque([0]), 0)
		while q:
			for _ in range(len(q)):
				cur = q.popleft()
				if cur == len(arr) - 1:
					return step
				neighbors = set([cur + 1, cur - 1] + [x for x in v2n[arr[cur]]])
				for nb in neighbors:
					if nb >= 0 and nb < len(arr) and (nb != cur) and (nb not in visited):
						visited.add(cur)
						q.append(nb)
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if not arr or len(arr) == 1:
			return 0
		dp = [float('inf')] * len(arr)
		dp[0] = 0
		position = collections.defaultdict(set)
		visited = {}
		for (i, e) in enumerate(arr):
			position[e].add(i)
			visited[i] = False
		visited[0] = True
		start = {0}
		step = 0
		while start:
			nextstart = set()
			for i in start:
				if i == len(arr) - 1:
					return step
				if i - 1 >= 0 and (not visited[i - 1]):
					dp[i - 1] = min(dp[i - 1], dp[i] + 1)
					nextstart.add(i - 1)
					visited[i - 1] = True
				if i + 1 < len(arr) and (not visited[i + 1]):
					dp[i + 1] = min(dp[i + 1], dp[i] + 1)
					nextstart.add(i + 1)
					visited[i + 1] = True
				for p in position[arr[i]]:
					if p != i and (not visited[p]):
						dp[p] = min(dp[p], dp[i] + 1)
						nextstart.add(p)
						visited[p] = True
				position[arr[i]].clear()
			start = nextstart
			step += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		val_to_ids = collections.defaultdict(list)
		_ = [val_to_ids[x].append(i) for (i, x) in enumerate(arr)]
		queue = collections.deque([(0, 0)])
		positions_seen = set()
		num_met = set()
		while queue:
			(i, dis) = queue.popleft()
			if i == len(arr) - 1:
				return dis
			val = arr[i]
			positions_seen.add(i)
			possible_indexes = []
			possible_indexes.append(i + 1)
			possible_indexes.append(i - 1)
			if len(val_to_ids[val]) > 1:
				for idx in val_to_ids[val]:
					if idx not in positions_seen:
						possible_indexes.append(idx)
				del val_to_ids[val]
			for p in possible_indexes:
				if p < 0 or p > len(arr) or p in positions_seen:
					continue
				queue.append((p, dis + 1))


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		dict_ = collections.defaultdict(list)
		for index in range(len(arr)):
			dict_[arr[index]].append(index)
		min_count = 0
		visited = set()
		visited.add((arr[0], 0))
		queue = collections.deque()
		queue.append((arr[0], 0))
		while queue:
			size = len(queue)
			for i in range(size):
				(curr_num, index) = queue.popleft()
				if index == len(arr) - 1:
					return min_count
				for (new_num, new_index) in self.move(curr_num, index, arr, dict_, visited):
					if (new_num, new_index) not in visited:
						visited.add((new_num, new_index))
						queue.append((new_num, new_index))
			min_count = min_count + 1

	def move(self, curr_num, index, arr, dict_, visited):
		for (new_num, new_index) in [(arr[index - 1], index - 1), (arr[index + 1], index + 1)]:
			if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
				yield (new_num, new_index)
		if dict_[curr_num]:
			new_num = curr_num
			for new_index in dict_[curr_num]:
				if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
					yield (new_num, new_index)
			del dict_[curr_num]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) < 2:
			return 0
		graph = {}
		for i in range(len(arr)):
			if arr[i] in graph:
				graph[arr[i]].append(i)
			else:
				graph[arr[i]] = [i]
		cur = [0]
		visited = {0}
		step = 0
		other = [len(arr) - 1]
		while cur:
			if len(cur) > len(other):
				(cur, other) = (other, cur)
			nex = []
			for i in cur:
				for node in graph[arr[i]]:
					if node in other:
						return step + 1
					if node not in visited:
						visited.add(node)
						nex.append(node)
				graph[arr[i]].clear()
				for x in [i + 1, i - 1]:
					if x in other:
						return step + 1
					if 0 <= x < len(arr) and x not in visited:
						visited.add(x)
						nex.append(x)
			cur = nex
			step += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		indexMap = collections.defaultdict(list)
		for (i, a) in enumerate(arr):
			indexMap[a].append(i)
		d = deque([(0, 0)])
		distance = 0
		visited = {0}
		while d:
			(node, distance) = d.popleft()
			if node == len(arr) - 1:
				return distance
			for nei in [node - 1, node + 1] + indexMap[arr[node]][::-1]:
				if 0 <= nei < len(arr) and nei != node and (nei not in visited):
					visited.add(nei)
					if nei == len(arr) - 1:
						return distance + 1
					d.append((nei, distance + 1))


from collections import defaultdict, deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		graph = defaultdict(list)
		for (i, num) in enumerate(arr):
			graph[num].append(i)
		curr = [0]
		visited = set([0])
		jumps = 0
		while curr:
			nxt = []
			for node in curr:
				if node == n - 1:
					return jumps
				for child in graph[arr[node]]:
					if child not in visited:
						visited.add(child)
						nxt.append(child)
				graph[arr[node]].clear()
				for child in (node - 1, node + 1):
					if 0 <= child < len(arr) and child not in visited:
						visited.add(child)
						nxt.append(child)
			curr = nxt
			jumps += 1


from collections import deque, defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		idxs = defaultdict(set)
		for (idx, e) in enumerate(arr):
			idxs[e].add(idx)

		def bfs(idx):
			q = deque([0])
			step = -1
			not_visited = set(range(len(arr) - 1, 0, -1))
			while q:
				step += 1
				for _ in range(len(q)):
					node = q.popleft()
					if node == len(arr) - 1:
						return step
					nxt_nodes = idxs[arr[node]]
					nxt_nodes = not_visited & nxt_nodes
					for nxt in [node - 1, node + 1]:
						if nxt in not_visited:
							nxt_nodes.add(nxt)
					if len(arr) - 1 in nxt_nodes:
						return step + 1
					not_visited.difference_update(nxt_nodes)
					nxt_nodes = nxt_nodes
					q.extend(nxt_nodes)
			return -1
		return bfs(0)


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		link = collections.defaultdict(list)
		for (i, x) in enumerate(arr):
			link[x].append(i)
		lvl = 0
		(num_met, pos_met) = (set(), set())
		queue = collections.deque([0])
		while queue:
			L = len(queue)
			for i in range(L):
				x = queue.popleft()
				if x == len(arr) - 1:
					return lvl
				num = arr[x]
				pos_met.add(x)
				for k in [x - 1, x + 1] + link[num] * (num not in num_met):
					if k in pos_met or not 0 <= k < len(arr):
						continue
					queue.append(k)
				num_met.add(num)
			lvl += 1
		return 0


from collections import defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n_arr = len(arr)
		if n_arr <= 1:
			return 0
		value_arr_map = defaultdict(list)
		for (i, n) in enumerate(arr):
			value_arr_map[n].append(i)
		head = [0]
		tail = [n_arr - 1]
		visited = {0, n_arr - 1}
		n_move = 0
		while head or tail:
			if len(head) > len(tail):
				(head, tail) = (tail, head)
			next_head = []
			for current_index in head:
				current_value = arr[current_index]
				candidates = []
				if current_value in value_arr_map:
					candidates += value_arr_map[current_value]
				if current_index < n_arr - 1:
					candidates += [current_index + 1]
				if current_index > 0:
					candidates += [current_index - 1]
				for cand in candidates:
					if cand in tail:
						return n_move + 1
					elif cand not in visited:
						visited.add(cand)
						next_head.append(cand)
			if current_value in value_arr_map:
				del value_arr_map[current_value]
			head = next_head
			n_move += 1
		raise ValueError()


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		print(len(arr))
		adj = collections.defaultdict(list)
		for (i, n) in enumerate(arr):
			adj[n].append(i)
		q = collections.deque()
		q.append((0, 0))
		used = [False] * len(arr)
		i = 0
		while q:
			(cur, step) = q.popleft()
			print(len(q))
			if cur == len(arr) - 1:
				return step
			if cur < len(arr) - 1 and (not used[cur + 1]):
				used[cur + 1] = True
				q.append((cur + 1, step + 1))
			if cur > 0 and (not used[cur - 1]):
				used[cur - 1] = True
				q.append((cur - 1, step + 1))
			for nxt in adj[arr[cur]]:
				if not used[nxt]:
					used[nxt] = True
					q.append((nxt, step + 1))
			adj[arr[cur]] = [k for k in adj[arr[cur]] if not used[k]]
		return -1


class Solution:

	def minJumps1(self, arr: List[int]) -> int:
		if not arr:
			return 0
		dp = [float('inf')] * len(arr)
		dp[0] = 0
		minIdx = {arr[0]: (0, 0)}
		for i in range(1, len(arr)):
			x = arr[i]
			stepRight = dp[i - 1] + 1
			jumpStep = minIdx[x][1] + 1 if x in minIdx else float('inf')
			dp[i] = min(stepRight, jumpStep)
			if x in minIdx:
				if dp[i] < minIdx[x][1]:
					minIdx[x] = (i, dp[i])
			else:
				minIdx[x] = (i, dp[i])
			j = i - 1
			while j >= 0 and dp[j] > dp[j + 1] + 1:
				dp[j] = dp[j + 1] + 1
				y = arr[j]
				if dp[j] < minIdx[y][1]:
					minIdx[y] = (j, dp[j])
				j -= 1
		return dp[-1]

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		graph = {}
		for i in range(n):
			if arr[i] in graph:
				graph[arr[i]].append(i)
			else:
				graph[arr[i]] = [i]
		curs = [0]
		visited = {0}
		step = 0
		while curs:
			nex = []
			for node in curs:
				if node == n - 1:
					return step
				for child in graph[arr[node]]:
					if child not in visited:
						visited.add(child)
						nex.append(child)
				graph[arr[node]].clear()
				for child in [node - 1, node + 1]:
					if 0 <= child < len(arr) and child not in visited:
						visited.add(child)
						nex.append(child)
			curs = nex
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		val_to_id = collections.defaultdict(set)
		id_to_neigh = {}
		for (i, val) in enumerate(arr):
			if not i or i == len(arr) - 1:
				val_to_id[val].add(i)
			elif not arr[i - 1] == arr[i] == arr[i + 1]:
				val_to_id[val].add(i)
		for (i, val) in enumerate(arr):
			if not i or i == len(arr) - 1:
				id_to_neigh[i] = set([i - 1, i + 1]) | val_to_id[val]
				id_to_neigh[i] -= set([-1, len(arr), i])
			elif not arr[i - 1] == arr[i] == arr[i + 1]:
				id_to_neigh[i] = set([i - 1, i + 1]) | val_to_id[val]
				id_to_neigh[i].remove(i)
		t = len(arr) - 1
		q = [(0, 0)]
		v = set([0])
		while q:
			level = []
			for (n, i) in q:
				if i == t:
					return n
				for j in id_to_neigh.get(i, []):
					if j not in v:
						v.add(j)
						level.append((n + 1, j))
			q = level


class Solution:

	def minJumps(self, a: List[int]) -> int:
		n = len(a)
		adj = defaultdict(list)
		for (i, x) in enumerate(a):
			adj[x].append(i)
		q = [(0, 0)]
		seen = [False] * n
		seen[0] = True
		for (u, d) in q:
			if u == n - 1:
				return d
			for v in (u - 1, u + 1):
				if 0 <= v < n and (not seen[v]):
					seen[v] = True
					q.append((v, d + 1))
			x = a[u]
			for v in adj[x]:
				if not seen[v]:
					seen[v] = True
					q.append((v, d + 1))
			if adj[x]:
				adj[x] = []


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		A = len(arr)
		m = defaultdict(list)
		for (i, n) in enumerate(arr):
			m[n].append(i)
		visited = set([-1])
		curr = set([0])
		for steps in itertools.count():
			visited.update(curr)
			if A - 1 in visited:
				return steps
			curr = {j for i in curr for j in [i - 1, i + 1] + m.pop(arr[i], []) if j not in visited}
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		nei = collections.defaultdict(list)
		for (i, x) in enumerate(arr):
			nei[x].append(i)
		frontier = collections.deque([(0, 0)])
		(num_met, pos_met) = (set(), set())
		while frontier:
			(pos, step) = frontier.popleft()
			if pos == len(arr) - 1:
				return step
			num = arr[pos]
			pos_met.add(pos)
			for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
				if p in pos_met or not 0 <= p < len(arr):
					continue
				frontier.append((p, step + 1))
			num_met.add(num)
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		to_index = {}
		for i in range(len(arr)):
			if arr[i] not in to_index:
				to_index[arr[i]] = []
			to_index[arr[i]].append(i)
		n = len(arr)
		q = [(0, 0)]
		vis = set([0])
		for (i, jumps) in q:
			if i == n - 1:
				return jumps
			if i + 1 < n and i + 1 not in vis:
				vis.add(i + 1)
				q.append((i + 1, jumps + 1))
			if i - 1 >= 0 and i - 1 not in vis:
				vis.add(i - 1)
				q.append((i - 1, jumps + 1))
			for j in to_index[arr[i]]:
				if j not in vis:
					q.append((j, jumps + 1))
					vis.add(j)
			to_index[arr[i]] = []
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		seen = set([0])
		dic = collections.defaultdict(set)
		for (i, num) in enumerate(arr):
			dic[num].add(i)
		bfs = collections.deque([[0, 0]])
		while bfs:
			(ind, c) = bfs.popleft()
			if ind == n - 1:
				return c
			for nind in [ind - 1, ind + 1]:
				if 0 <= nind < n and nind not in seen:
					bfs.append([nind, c + 1])
					seen.add(nind)
			for child in dic[arr[ind]]:
				if child not in seen:
					seen.add(child)
					bfs.append([child, c + 1])
			dic[arr[ind]] = set()


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		index = {}
		if len(set(arr)) > 10:
			for (ic, val) in enumerate(arr):
				index[val] = index.get(val, []) + [ic]
		else:
			for val in set(arr):
				index[val] = [ic for (ic, v0) in enumerate(arr) if v0 == val]
		neigh = {}
		for (ic, val) in enumerate(arr):
			if ic - 1 >= 0:
				neigh[ic] = neigh.get(ic, []) + [ic - 1]
			if ic + 1 < len(arr):
				neigh[ic] = neigh.get(ic, []) + [ic + 1]
		front = [0]
		visited = {0: 0}
		checkedvalues = set()
		while front != []:
			nf = []
			for u in front:
				val = arr[u]
				for v in neigh.get(u, []):
					if not v in visited:
						visited[v] = visited[u] + 1
						nf.append(v)
				if not val in checkedvalues:
					for v in index[val] + neigh.get(u, []):
						if not v in visited:
							visited[v] = visited[u] + 1
							nf.append(v)
				checkedvalues.add(val)
			front = nf
		return visited.get(len(arr) - 1, -1)


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		L = len(arr)
		if L < 2:
			return 0
		cnt = defaultdict(list)
		for (i, val) in enumerate(arr):
			cnt[val].append(i)
		q = deque([0])
		visited = {0}
		steps = 0
		while q:
			size = len(q)
			for _ in range(size):
				n = q.popleft()
				if n == L - 1:
					return steps
				for el in cnt[arr[n]]:
					if el not in visited:
						q.append(el)
						visited.add(el)
				cnt[arr[n]].clear()
				for c in [n - 1, n + 1]:
					if 0 <= c < L and c not in visited:
						q.append(c)
						visited.add(c)
			steps += 1
		return steps


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		maps = collections.defaultdict(list)
		[maps[a].append(i) for (i, a) in enumerate(arr)]
		begins = set([0])
		ends = set([len(arr) - 1])
		visitedIdx = set([-1, len(arr)])
		for steps in range(len(arr)):
			if len(begins) > len(ends):
				(begins, ends) = (ends, begins)
			nextLevels = set()
			for b in begins:
				if b in ends:
					return steps
				if b in visitedIdx:
					continue
				visitedIdx.add(b)
				nextLevels.update([b - 1, b + 1] + maps[arr[b]])
				maps.pop(arr[b])
			begins = nextLevels


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		d = defaultdict(list)
		n = len(arr)
		for i in range(n):
			d[arr[i]].append(i)
		vis = [0] * n
		vis[0] = 1
		q = [(0, 0)]
		while q:
			(i, k) = q.pop(0)
			for j in d[arr[i]] + [i - 1, i + 1]:
				if j < 0 or j >= n or vis[j]:
					continue
				if j == n - 1:
					return k + 1
				vis[j] = 1
				q.append((j, k + 1))
			d[arr[i]] = []
		return 0


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		arr = [x for (i, x) in enumerate(arr) if i == 0 or i == len(arr) - 1 or x != arr[i - 1] or (x != arr[i + 1])]
		d = {}
		for (i, x) in enumerate(arr):
			d.setdefault(x, set()).add(i)
		adj = {}
		for (i, x) in enumerate(arr):
			adj[i] = set()
			if i != 0:
				adj[i].add(i - 1)
			if i != len(arr) - 1:
				adj[i].add(i + 1)
			adj[i] |= d[arr[i]]
			adj[i].remove(i)
		q = collections.deque()
		distance = [len(arr) - 1] * len(arr)
		q.append(0)
		count = 0
		while q:
			nxt_q = collections.deque()
			while q:
				nxt = q.popleft()
				if distance[nxt] <= count:
					continue
				distance[nxt] = count
				for x in adj[nxt]:
					nxt_q.append(x)
			q = nxt_q
			count += 1
		return distance[-1]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		A = arr
		n = len(A)
		q = []
		val_dic = collections.defaultdict(list)
		for (i, val) in enumerate(A):
			if len(val_dic[val]) > 0:
				last_range = val_dic[val][-1]
				if last_range[1] + 1 == i:
					last_range[1] = i
				else:
					val_dic[val].append([i, i])
			else:
				val_dic[val].append([i, i])
		walked_val = set()
		q.append(0)
		walked = set()
		steps = -1
		while len(q) > 0:
			cur_len = len(q)
			next_q = []
			for i in q:
				val = A[i]
				if i == n - 1:
					return steps + 1
				walked.add(i)
				if i + 1 < n and i + 1 not in walked:
					next_q.append(i + 1)
				if i - 1 > -1 and i - 1 not in walked:
					next_q.append(i - 1)
				if val not in walked_val:
					index_range_list = val_dic[val]
					for index_range in index_range_list:
						for j in (index_range[0], index_range[1]):
							if j != i and j not in walked:
								next_q.append(j)
						walked_val.add(val)
			steps += 1
			q = next_q
		return steps


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		N = len(arr)
		indices = collections.defaultdict(set)
		for (i, a) in enumerate(arr):
			indices[a].add(i)
		queue = collections.deque([(0, 0)])
		seen = {0}
		value_seen = set()
		while queue:
			(i, move) = queue.popleft()
			if i == N - 1:
				return move
			if arr[i] not in value_seen:
				value_seen.add(arr[i])
				for j in indices[arr[i]]:
					if j != i and j not in seen:
						seen.add(j)
						queue.append((j, move + 1))
			if i - 1 >= 0 and i - 1 not in seen:
				seen.add(i - 1)
				queue.append((i - 1, move + 1))
			if i + 1 < N and i + 1 not in seen:
				seen.add(i + 1)
				queue.append((i + 1, move + 1))


import numpy as np
import heapq
from collections import deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		self.arr = arr
		self.val2indx = {}
		for (i, v) in enumerate(arr):
			if not v in self.val2indx:
				self.val2indx[v] = []
			self.val2indx[v].append(i)
		self.solutions = [np.inf for i in range(len(arr))]
		self.solutions[-1] = 0
		self.visited = [False for i in range(len(arr))]
		node_q = deque()
		node_q.append((0, len(arr) - 1))
		while node_q:
			(dist, indx) = node_q.popleft()
			self.visited[indx] = True
			if dist > self.solutions[indx]:
				continue
			(next_indx, prev_indx) = (min(indx + 1, len(self.arr) - 1), max(indx - 1, 0))
			indices = [i for i in self.val2indx[self.arr[indx]] if i != indx and i != prev_indx and (i != next_indx) and (not self.visited[i])]
			indices = [prev_indx, next_indx] + indices
			if not self.visited[prev_indx]:
				indices.append(prev_indx)
			if not self.visited[next_indx]:
				indices.append(next_indx)
			for j in indices:
				newdist = dist + 1
				if np.isinf(self.solutions[j]) or (newdist < self.solutions[j] and (not self.visited[j])):
					self.solutions[j] = newdist
					node_q.append((newdist, j))
					self.visited[j] = True
					if j == 0:
						return newdist
		return self.solutions[0]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		s = defaultdict(list)
		for (i, num) in enumerate(arr):
			s[num] += [i]
		q = set([0])
		seen = set()
		level = 0
		while q:
			seen.update(q)
			new_q = set()
			for i in q:
				if i == len(arr) - 1:
					return level
				children = []
				if i + 1 < len(arr):
					children += [i + 1]
				if i - 1 >= 0:
					children += [i - 1]
				for j in s[arr[i]]:
					if j != i:
						children += [j]
				del s[arr[i]]
				for child in children:
					if child not in seen:
						new_q.add(child)
			level += 1
			q = new_q


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		d = {}
		seen = set()
		queue = deque([(0, 0)])
		for (i, num) in enumerate(arr):
			if i == 0 or i == len(arr) - 1 or (arr[i - 1] != arr[i] or arr[i + 1] != arr[i]):
				d[num] = d.get(num, []) + [i]
		while queue:
			(next_idx, steps) = queue.popleft()
			if next_idx == len(arr) - 1:
				return steps
			if next_idx + 1 <= len(arr) and next_idx + 1 not in seen:
				queue.append((next_idx + 1, steps + 1))
				seen.add(next_idx + 1)
			if next_idx - 1 >= 0 and next_idx - 1 not in seen:
				queue.append((next_idx - 1, steps + 1))
				seen.add(next_idx - 1)
			for i in d[arr[next_idx]][::-1]:
				if i != next_idx and i not in seen:
					queue.append((i, steps + 1))
					seen.add(i)
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		record = collections.defaultdict(list)
		for (i, v) in enumerate(arr):
			record[v].append(i)
		nums = set()
		pos_met = set()
		q = collections.deque([(0, 0)])
		while q:
			(pos, step) = q.popleft()
			if pos == len(arr) - 1:
				return step
			num = arr[pos]
			pos_met.add(pos)
			temp = [pos - 1, pos + 1]
			if num not in nums:
				for j in record[num]:
					temp += [j]
			nums.add(num)
			for i in temp:
				if 0 <= i < len(arr) and i not in pos_met:
					q.append([i, step + 1])


class Solution:

	def minJumps(self, arr: List[int]) -> int:

		def BFS(queue):
			seen = [1] * len(arr)
			seen[0] = 0
			while queue:
				(var, level) = queue.pop(0)
				if var == len(arr) - 1:
					return level
				if seen[var + 1]:
					queue.append([var + 1, level + 1])
					seen[var + 1] = 0
				if var - 1 >= 0 and seen[var - 1]:
					queue.append([var - 1, level + 1])
					seen[var - 1] = 0
				for i in d[arr[var]]:
					if seen[i]:
						queue.append([i, level + 1])
						seen[i] = 0
				d[arr[var]].clear()
		d = defaultdict(list)
		for i in range(len(arr) - 1, -1, -1):
			d[arr[i]] += [i]
		return BFS([[0, 0]])


from collections import defaultdict, deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		VALUE_INDEX_MAP = defaultdict(list)
		for (i, v) in enumerate(arr):
			VALUE_INDEX_MAP[v].append(i)
		queue = deque([0])
		seen = set([0])
		nsteps = -1
		while queue:
			levelSize = len(queue)
			nsteps += 1
			for _ in range(levelSize):
				x = queue.popleft()
				if x == len(arr) - 1:
					return nsteps
				for nx in VALUE_INDEX_MAP[arr[x]] + [x - 1, x + 1]:
					if 0 <= nx < len(arr) and nx not in seen:
						queue.append(nx)
						seen.add(nx)
				VALUE_INDEX_MAP[arr[x]].clear()
		return -1


from collections import deque
from collections import defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		mapping = defaultdict(set)
		for (i, val) in enumerate(arr):
			mapping[val].add(i)
		queue = deque([(0, 0)])
		visited = set([0])
		while queue:
			(curr_cost, ci) = queue.popleft()
			if ci == len(arr) - 1:
				return curr_cost
			if ci + 1 < len(arr) and ci + 1 not in visited:
				queue.append((curr_cost + 1, ci + 1))
				visited.add(ci + 1)
				if ci + 1 in mapping[arr[ci]]:
					mapping[arr[ci]].remove(ci + 1)
			if ci - 1 >= 0 and ci - 1 not in visited:
				queue.append((curr_cost + 1, ci - 1))
				visited.add(ci - 1)
				if ci - 1 in mapping[arr[ci]]:
					mapping[arr[ci]].remove(ci - 1)
			next_ = set(mapping[arr[ci]])
			for ni in next_:
				if ni not in visited:
					queue.append((curr_cost + 1, ni))
					visited.add(ni)
				mapping[arr[ci]].remove(ni)
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if not arr or len(arr) == 1:
			return 0
		val_to_idxes = collections.defaultdict(list)
		adj = collections.defaultdict(set)
		for i in range(len(arr)):
			val_to_idxes[arr[i]].append(i)
		q = [(0, 0)]
		visited = {0}
		while q:
			(idx, dist) = q.pop(0)
			if idx == len(arr) - 1:
				return dist
			visited.add(idx)
			for neighbor in val_to_idxes[arr[idx]]:
				if neighbor in visited:
					continue
				q.append((neighbor, dist + 1))
				visited.add(neighbor)
				if neighbor == len(arr) - 1:
					return dist + 1
			if idx - 1 >= 0 and idx - 1 not in visited:
				q.append((idx - 1, dist + 1))
				visited.add(idx - 1)
			if idx + 1 < len(arr) and idx + 1 not in visited:
				q.append((idx + 1, dist + 1))
				visited.add(idx + 1)
				if idx + 1 == len(arr) - 1:
					return dist + 1
			val_to_idxes[arr[idx]] = []
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		dic = defaultdict(list)
		for i in range(len(arr)):
			dic[arr[i]].append(i)
		visited = [False] * len(arr)
		queue = collections.deque()
		queue.append((0, 0))
		ans = 0
		N = len(arr)
		while queue:
			(i, step) = queue.popleft()
			print((i, step))
			if i == N - 1:
				ans = step
				break
			if visited[i] == False:
				if i + 1 < N:
					queue.append((i + 1, step + 1))
				if i - 1 >= 0:
					queue.append((i - 1, step + 1))
				for index in dic[arr[i]]:
					if visited[index] == False:
						queue.append((index, step + 1))
				visited[i] = True
				dic[arr[i]] = []
		return ans


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n < 2:
			return 0
		graph = defaultdict(list)
		for (i, v) in enumerate(arr):
			graph[v].append(i)
		queue = [0]
		seen = {0}
		steps = 0
		while queue:
			next_ = []
			for node in queue:
				if node == n - 1:
					return steps
				for neighbor in graph[arr[node]]:
					if neighbor not in seen:
						seen.add(neighbor)
						next_.append(neighbor)
				for neighbor in [node - 1, node + 1]:
					if 0 <= neighbor < n and neighbor not in seen:
						seen.add(neighbor)
						next_.append(neighbor)
				graph[arr[node]].clear()
			queue = next_
			steps += 1
		return -1


import collections

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		d = collections.defaultdict(list)
		for (index, element) in enumerate(arr):
			d[element].append(index)
		queue = collections.deque([(0, 0)])
		s = set()
		s.add(0)
		while len(queue):
			(currIndex, jumps) = queue.popleft()
			for nextIndex in [currIndex + 1, currIndex - 1] + d[arr[currIndex]][::-1]:
				if nextIndex < len(arr) and nextIndex > -1 and (nextIndex != currIndex) and (nextIndex not in s):
					if nextIndex == len(arr) - 1:
						return jumps + 1
					s.add(nextIndex)
					queue.append((nextIndex, jumps + 1))
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		minJump = len(arr) + 1
		graph = {}
		for (i, n) in enumerate(arr):
			if 1 < i < len(arr) - 1 and arr[i - 1] == arr[i] == arr[i + 1]:
				continue
			graph[n] = graph.get(n, [])
			graph[n].append(i)
		queue = collections.deque([0])
		visited = set([0])
		step = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				node = queue.popleft()
				if node == len(arr) - 1:
					return step
				num = graph.pop(arr[node], [])
				for nei in [node + 1, node - 1] + num:
					if nei not in visited and 0 <= nei < len(arr):
						queue.append(nei)
						visited.add(nei)
			step += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n == 1:
			return 0
		if arr[-1] == arr[0]:
			return 1
		mapping = collections.defaultdict(list)
		for (i, num) in enumerate(arr):
			mapping[num].append(i)
		q = collections.deque([(0, 0)])
		visited = set([0])
		while q:
			(cur_i, jumps) = q.popleft()
			if cur_i == n - 1:
				return jumps
			curnum = arr[cur_i]
			for nei_i in mapping[curnum]:
				if nei_i != cur_i and nei_i not in visited:
					visited.add(nei_i)
					q.append((nei_i, jumps + 1))
			mapping[curnum] = []
			if cur_i + 1 < n and cur_i + 1 not in visited:
				visited.add(cur_i + 1)
				q.append((cur_i + 1, jumps + 1))
			if cur_i - 1 >= 0 and cur_i - 1 not in visited:
				visited.add(cur_i - 1)
				q.append((cur_i - 1, jumps + 1))
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		c = collections.defaultdict(list)
		for (i, x) in enumerate(arr):
			c[x].append(i)
		q = [0]
		steps = [0] * len(arr)
		steps[0] = 1
		seen = set()
		while q:
			i = q.pop(0)
			if i == len(arr) - 1:
				return steps[i] - 1
			children = [i - 1, i + 1]
			if arr[i] not in seen:
				children += c[arr[i]][::-1]
				seen.add(arr[i])
			for child in children:
				if child < 0 or child >= len(arr):
					continue
				if child == i:
					continue
				if steps[child]:
					continue
				steps[child] = steps[i] + 1
				q.append(child)
		return steps[-1] - 1


from collections import defaultdict, deque
import heapq

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		d = defaultdict(set)
		for (i, x) in enumerate(arr):
			d[x].add(i)
		(q, s) = ([(0, 0)], defaultdict(lambda : float('inf')))
		s[0] = 0
		while q:
			(m, i) = heapq.heappop(q)
			i = -i
			if i - 1 >= 0 and s[i - 1] > m + 1:
				s[i - 1] = m + 1
				heapq.heappush(q, (m + 1, -(i - 1)))
			if i + 1 < n and s[i + 1] > m + 1:
				if i + 1 == n - 1:
					return m + 1
				s[i + 1] = m + 1
				heapq.heappush(q, (m + 1, -(i + 1)))
			(x, js) = (arr[i], set())
			for j in d[x]:
				if s[j] > m + 1:
					if j == n - 1:
						return m + 1
					s[j] = m + 1
					heapq.heappush(q, (m + 1, -j))
				else:
					js.add(j)
			for j in js:
				d[x].remove(j)
		return s[n - 1]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		graph = defaultdict(list)
		for (i, num) in enumerate(arr):
			graph[num].append(i)
		q = deque([0])
		counter = 0
		visited = [0] * len(arr)
		visited[0] = 1
		while q:
			size = len(q)
			for _ in range(size):
				i = q.popleft()
				if i == len(arr) - 1:
					return counter
				num = arr[i]
				neighbors = graph[num]
				for neighbor in neighbors:
					if not visited[neighbor]:
						q.append(neighbor)
						visited[neighbor] = 1
				graph.pop(num)
				if i + 1 < len(arr) and (not visited[i + 1]):
					q.append(i + 1)
					visited[i + 1] = 1
				if i - 1 >= 0 and (not visited[i - 1]):
					q.append(i - 1)
					visited[i - 1] = 1
			counter += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		endpos = len(arr) - 1
		graph = {}
		for (i, n) in enumerate(arr):
			if n not in graph:
				graph[n] = []
			graph[n].append(i)
		curr = set([0])
		hit = set()
		mark = 0
		while curr:
			nxt = set()
			for i in curr:
				hit.add(i)
				if i == endpos:
					return mark
				if i != 0 and i - 1 not in hit:
					nxt.add(i - 1)
				if i + 1 not in hit:
					nxt.add(i + 1)
				if arr[i] in graph:
					nxt.update([j for j in graph[arr[i]] if i != j and j not in hit])
					del graph[arr[i]]
			mark += 1
			curr = nxt
		return -1


class Solution:

	def minJumps(self, arr) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		graph = {}
		for i in range(n):
			if arr[i] in graph:
				graph[arr[i]].append(i)
			else:
				graph[arr[i]] = [i]
		curs = [0]
		visited = {0, n - 1}
		step = 0
		other = [n - 1]
		while curs:
			if len(curs) > len(other):
				(curs, other) = (other, curs)
			nex = []
			for node in curs:
				for child in graph[arr[node]]:
					if child in other:
						return step + 1
					if child not in visited:
						visited.add(child)
						nex.append(child)
				graph[arr[node]].clear()
				for child in [node - 1, node + 1]:
					if child in other:
						return step + 1
					if 0 <= child < len(arr) and child not in visited:
						visited.add(child)
						nex.append(child)
			curs = nex
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		i = 0
		while i < len(arr) - 2:
			if arr[i] == arr[i + 1] == arr[i + 2]:
				arr.pop(i)
			else:
				i += 1

		def jump(i):
			nexts = []
			if i - 1 >= 0:
				nexts.append(i - 1)
			if i + 1 < len(arr):
				nexts.append(i + 1)
			for index in d[arr[i]]:
				if index != i:
					nexts.append(index)
			return nexts
		d = {}
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] in d:
				d[arr[i]].add(i)
			else:
				d[arr[i]] = {i}
		for (k, v) in list(d.items()):
			d[k] = list(v)
			d[k].sort(reverse=True)
		q = deque()
		visited = set()
		q.append(0)
		visited.add(0)
		steps = -1
		while q:
			size = len(q)
			steps += 1
			for i in range(size):
				pop_index = q.popleft()
				if pop_index == len(arr) - 1:
					return steps
				for nex in jump(pop_index):
					if nex not in visited:
						q.append(nex)
						visited.add(nex)
		return -1


from collections import defaultdict, deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		g = defaultdict(list)
		for (i, n) in enumerate(arr):
			g[n].append(i)
		cur = [0]
		step = 0
		seen = {0}
		while cur:
			nex = []
			for i in cur:
				if i == len(arr) - 1:
					return step
				for adj in g[arr[i]]:
					if adj not in seen:
						seen.add(adj)
						nex.append(adj)
				g[arr[i]].clear()
				if i - 1 >= 0 and i - 1 not in seen:
					seen.add(i - 1)
					nex.append(i - 1)
				if i + 1 < len(arr) and i + 1 not in seen:
					seen.add(i + 1)
					nex.append(i + 1)
			step += 1
			cur = nex
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		dic = {}
		for (i, num) in enumerate(arr):
			if num not in dic:
				dic[num] = set()
			dic[num].add(i)
		bag = set(list(range(1, len(arr))))
		queue = [0]
		res = 0
		print(bag)
		while len(queue) > 0:
			l = len(queue)
			for _ in range(l):
				node = queue.pop(0)
				if node == len(arr) - 1:
					return res
				if node > 0:
					if node - 1 in bag:
						queue.append(node - 1)
						bag.remove(node - 1)
						if arr[node - 1] in dic and node - 1 in dic[arr[node - 1]]:
							dic[arr[node - 1]].remove(node - 1)
							if not dic[arr[node - 1]]:
								del dic[arr[node - 1]]
				if node < len(arr) - 1:
					if node + 1 in bag:
						queue.append(node + 1)
						bag.remove(node + 1)
						if arr[node - 1] in dic and node - 1 in dic[arr[node - 1]]:
							dic[arr[node - 1]].remove(node - 1)
							if not dic[arr[node - 1]]:
								del dic[arr[node - 1]]
				if arr[node] in dic:
					for i in dic[arr[node]]:
						if i in bag:
							bag.remove(i)
							queue.append(i)
					del dic[arr[node]]
			res += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		g = collections.defaultdict(list)
		for (i, v) in enumerate(arr):
			g[v].append(i)
		visit = [0] * n
		values = set()
		step = 0
		q = [0]
		while q:
			size = len(q)
			for _ in range(size):
				cur = q.pop(0)
				if cur == n - 1:
					return step
				for i in [cur - 1, cur + 1]:
					if 0 <= i < n and (not visit[i]):
						visit[i] = 1
						q.append(i)
				if arr[cur] not in values:
					values.add(arr[cur])
					for i in g[arr[cur]]:
						if not visit[i]:
							visit[i] = 1
							q.append(i)
			step += 1
		return step


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		v_jumped = set()
		v_idx = collections.defaultdict(list)
		for (i, v) in enumerate(arr):
			v_idx[v].append(i)
		q = [0]
		seen_idx = {0}
		step = 0
		while q:
			sz = len(q)
			for _ in range(sz):
				i = q.pop(0)
				if i == len(arr) - 1:
					return step
				if arr[i] not in v_jumped:
					v_jumped.add(arr[i])
					for j in v_idx[arr[i]]:
						if j not in seen_idx:
							seen_idx.add(j)
							q.append(j)
				if i + 1 < len(arr) and i + 1 not in seen_idx:
					seen_idx.add(i + 1)
					q.append(i + 1)
				if i - 1 >= 0 and i - 1 not in seen_idx:
					seen_idx.add(i - 1)
					q.append(i - 1)
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:

		def BFS(queue):
			(seen, val_seen) = ([1] * len(arr), set())
			seen[0] = 0
			while queue:
				(var, level) = queue.pop(0)
				if var == len(arr) - 1:
					return level
				if seen[var + 1]:
					queue.append([var + 1, level + 1])
					seen[var + 1] = 0
				if var - 1 >= 0 and seen[var - 1]:
					queue.append([var - 1, level + 1])
					seen[var - 1] = 0
				if arr[var] not in val_seen:
					for i in d[arr[var]]:
						if seen[i]:
							queue.append([i, level + 1])
							seen[i] = 0
				val_seen.add(arr[var])
		d = defaultdict(list)
		for (i, v) in enumerate(arr):
			d[v] += [i]
		return BFS([[0, 0]])


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		g = collections.defaultdict(list)
		for (i, num) in enumerate(arr):
			g[num].append(i)
		visited = set()
		q = deque([(0, 0)])
		while q:
			(idx, step) = q.popleft()
			if idx == len(arr) - 1:
				return step
			visited.add(idx)
			for n_idx in [idx - 1, idx + 1] + g[arr[idx]]:
				if n_idx not in visited and 0 <= n_idx < len(arr):
					q.append((n_idx, step + 1))
			del g[arr[idx]]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		record = {}
		for (idx, item) in enumerate(arr, 0):
			if item not in record:
				record[item] = [idx]
			elif record[item][-1] + 2 >= idx:
				record[item][-1] = idx
			else:
				record[item].append(idx)
		queue = [0]
		ret = [-1] * len(arr)
		ret[0] = 0
		step = 0
		last = len(arr) - 1
		while queue:
			target = []
			step += 1
			for idx in queue:
				if idx > 0 and ret[idx - 1] == -1:
					target.append(idx - 1)
					ret[idx - 1] = step
				if idx + 1 < len(arr) and ret[idx + 1] == -1:
					target.append(idx + 1)
					ret[idx + 1] = step
					if idx + 1 == last:
						return step
				for pos in record[arr[idx]]:
					if pos == idx:
						continue
					if ret[pos] == -1:
						target.append(pos)
						ret[pos] = step
						if pos == last:
							return step
			queue = target
		return ret[-1]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		dic = collections.defaultdict(list)
		for (i, num) in enumerate(arr):
			dic[num].append(i)
		queue = [0]
		pos_visited = set([0])
		num_visited = set()
		step = 0
		while queue:
			for _ in range(len(queue)):
				cur = queue.pop(0)
				if cur == n - 1:
					return step
				for nextIdx in [cur - 1, cur + 1] + dic[arr[cur]] * (arr[cur] not in num_visited):
					if 0 <= nextIdx < n and nextIdx not in pos_visited:
						pos_visited.add(nextIdx)
						queue.append(nextIdx)
				num_visited.add(arr[cur])
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		N = len(arr)
		last_idx = N - 1
		indices = collections.defaultdict(set)
		for (i, a) in enumerate(arr):
			indices[a].add(i)
		moves = [None] * N
		moves[0] = 0
		edges = []
		idx = 0
		seen_values = set()

		def reachables(i):
			idx_set = set()
			if arr[i] not in seen_values:
				seen_values.add(arr[i])
				idx_set |= indices[arr[i]]
			if i - 1 >= 0:
				idx_set.add(i - 1)
			if i + 1 < N:
				idx_set.add(i + 1)
			if i in idx_set:
				idx_set.remove(i)
			return idx_set
		while idx != last_idx:
			for j in reachables(idx):
				if moves[j] is None:
					heapq.heappush(edges, (moves[idx] + 1, j))
			(move, idx) = heapq.heappop(edges)
			moves[idx] = move
		return moves[idx]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		seen = {0}
		q = [0]
		goal = len(arr) - 1
		linked = collections.defaultdict(list)
		for (idx, x) in enumerate(arr):
			linked[x].append(idx)
		q_back = [goal]
		q = [0]
		levels = -1
		while q:
			levels += 1
			q_len = len(q)
			for _ in range(q_len):
				idx = q.pop(0)
				if idx == goal:
					return levels
				if idx + 1 not in seen:
					q.append(idx + 1)
					seen.add(idx + 1)
				if idx > 0 and idx - 1 not in seen:
					q.append(idx - 1)
					seen.add(idx - 1)
				for link in linked[arr[idx]]:
					if link not in seen:
						q.append(link)
						seen.add(link)
				del linked[arr[idx]]


class Solution:

	def minJumps(self, nums):
		neighbors = defaultdict(list)
		_ = [neighbors[num].append(i) for (i, num) in enumerate(nums)]
		q = deque([(0, 0)])
		(num_seen, pos_seen) = (set(), set())
		while q:
			(pos, step) = q.popleft()
			if pos == len(nums) - 1:
				return step
			num = nums[pos]
			pos_seen.add(pos)
			for p in [pos - 1, pos + 1] + neighbors[num] * (num not in num_seen):
				if p in pos_seen or not 0 <= p < len(nums):
					continue
				q.append((p, step + 1))
			num_seen.add(num)


from collections import defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		m = defaultdict(list)
		for i in range(len(arr)):
			m[arr[i]].append(i)
		start = (0, 0)
		queue = [start]
		visited = set([0])
		while queue != []:
			current = queue.pop(0)
			if current[0] == len(arr) - 1:
				return current[1]
			if current[0] + 1 < len(arr) and current[0] + 1 not in visited:
				queue.append((current[0] + 1, current[1] + 1))
				visited.add(current[0] + 1)
			if current[0] - 1 >= 0 and current[0] - 1 not in visited:
				queue.append((current[0] - 1, current[1] + 1))
				visited.add(current[0] - 1)
			for n in m[arr[current[0]]]:
				if n not in visited:
					queue.append((n, current[1] + 1))
					visited.add(n)
			if arr[n] in m:
				del m[arr[n]]


from collections import defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		pos_m = defaultdict(set)
		for (idx, val) in enumerate(arr):
			pos_m[val].add(idx)
		visited = [float('inf') for i in range(len(arr))]
		seen = set([0])
		steps = 0
		pos_m[arr[0]].remove(0)
		q = [(0, 0)]
		while q:
			for _ in range(len(q)):
				(idx, step) = q.pop(0)
				if idx == len(arr) - 1:
					return step
				if idx > 0 and idx - 1 not in seen:
					seen.add(idx - 1)
					q.append((idx - 1, step + 1))
				if idx + 1 < len(arr) and idx + 1 not in seen:
					seen.add(idx + 1)
					q.append((idx + 1, step + 1))
				for pos in pos_m[arr[idx]]:
					if pos not in seen:
						seen.add(pos)
						q.append((pos, step + 1))
				del pos_m[arr[idx]]
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		return self.minJumpsBiBFS(arr)

	def bfs(self, arr: List[int]):
		arrLen = len(arr)
		if arrLen <= 1:
			return 0
		adjList = defaultdict(set)
		for i in range(len(arr)):
			adjList[arr[i]].add(i)
		queue = deque([0])
		visited = set([0])
		jump = 0
		while queue:
			length = len(queue)
			for _ in range(length):
				node = queue.popleft()
				for nei in adjList[arr[node]]:
					if nei == arrLen - 1:
						return jump + 1
					if nei in visited:
						continue
					visited.add(nei)
					queue.append(nei)
				adjList[arr[node]].clear()
				if node + 1 < arrLen:
					if node + 1 == arrLen - 1:
						return jump + 1
					if node + 1 not in visited:
						visited.add(node + 1)
						queue.append(node + 1)
				if node - 1 >= 0:
					if node - 1 == arrLen - 1:
						return jump + 1
					if node - 1 not in visited:
						visited.add(node - 1)
						queue.append(node - 1)
			jump += 1
		return -1

	def minJumpsBiBFS(self, arr: List[int]) -> int:
		arrLen = len(arr)
		if arrLen <= 1:
			return 0
		adjList = defaultdict(set)
		for i in range(len(arr)):
			adjList[arr[i]].add(i)
		frontQueue = deque([0])
		rearQueue = deque([len(arr) - 1])
		visited = set([0])
		jump = 0
		while frontQueue or rearQueue:
			if len(frontQueue) > len(rearQueue):
				(frontQueue, rearQueue) = (rearQueue, frontQueue)
			length = len(frontQueue)
			for _ in range(length):
				node = frontQueue.popleft()
				for nei in adjList[arr[node]]:
					if nei in rearQueue:
						return jump + 1
					if nei in visited:
						continue
					visited.add(nei)
					frontQueue.append(nei)
				adjList[arr[node]].clear()
				if node + 1 < arrLen:
					if node + 1 in rearQueue:
						return jump + 1
					if node + 1 not in visited:
						visited.add(node + 1)
						frontQueue.append(node + 1)
				if node - 1 >= 0:
					if node - 1 in rearQueue:
						return jump + 1
					if node - 1 not in visited:
						visited.add(node - 1)
						frontQueue.append(node - 1)
			jump += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		else:
			num_indices = defaultdict(list)
			for i in range(len(arr) - 1, -1, -1):
				num_indices[arr[i]].append(i)
			visited = {0}
			queue = deque()
			queue.append((0, 0))
			while queue:
				(i, steps) = queue.popleft()
				for j in [i - 1, i + 1] + num_indices[arr[i]]:
					if j not in visited and 0 <= j < len(arr):
						if j == len(arr) - 1:
							return steps + 1
						else:
							queue.append((j, steps + 1))
							visited.add(j)


from collections import defaultdict
from collections import deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		indexes = defaultdict(list)
		for (i, v) in enumerate(arr):
			if i == 0 or arr[i - 1] != v:
				indexes[v].append(i)
		queue = deque([(0, True), (len(arr) - 1, False)])
		minimum_steps = {0: 0}
		minimum_steps_negative = {len(arr) - 1: 0}
		while queue:
			(curPos, direction) = queue.popleft()
			if direction and curPos in minimum_steps_negative:
				return minimum_steps_negative[curPos] + minimum_steps[curPos]
			if not direction and curPos in minimum_steps:
				return minimum_steps_negative[curPos] + minimum_steps[curPos]
			candidates = []
			if curPos > 0:
				candidates.append(curPos - 1)
			if curPos < len(arr) - 1:
				candidates.append(curPos + 1)
			candidates.extend(indexes[arr[curPos]])
			ans = []
			for i in candidates:
				if direction:
					checker = minimum_steps
				else:
					checker = minimum_steps_negative
				if i not in checker:
					checker[i] = checker[curPos] + 1
					queue.append((i, direction))


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		arr_f = []
		prev = None
		repeat = 0
		for num in arr:
			if num == prev:
				if repeat == 2:
					continue
				repeat += 1
			else:
				prev = num
				repeat = 0
			arr_f.append(num)
		n = len(arr_f)
		graph = {}
		for i in range(n):
			if arr_f[i] in graph:
				graph[arr_f[i]].append(i)
			else:
				graph[arr_f[i]] = [i]
		curs = [0]
		visited = {0}
		step = 0
		while curs:
			nex = []
			for node in curs:
				if node == n - 1:
					return step
				for child in graph[arr_f[node]]:
					if child not in visited:
						visited.add(child)
						nex.append(child)
				graph[arr_f[node]].clear()
				for child in [node - 1, node + 1]:
					if 0 <= child < n and child not in visited:
						visited.add(child)
						nex.append(child)
			curs = nex
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		map = collections.defaultdict(list)
		for (i, a) in enumerate(arr):
			map[a].append(i)
		(visited, visiting) = ({-1}, {0})
		for steps in itertools.count():
			visited |= visiting
			if len(arr) - 1 in visited:
				return steps
			visiting = {j for i in visiting for j in [i - 1, i + 1] + map.pop(arr[i], [])} - visited


from collections import deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		graph = collections.defaultdict(list)
		for (i, num) in enumerate(arr):
			graph[num].append(i)
		queue = deque([0])
		visited = set([0])
		steps = 0
		while queue:
			level_size = len(queue)
			for _ in range(level_size):
				curr_idx = queue.popleft()
				if curr_idx == n - 1:
					return steps
				for nxt_idx in [curr_idx - 1, curr_idx + 1] + graph[arr[curr_idx]][::-1]:
					if 0 <= nxt_idx < n and nxt_idx not in visited:
						if nxt_idx == n - 1:
							return steps + 1
						queue.append(nxt_idx)
						visited.add(nxt_idx)
			steps += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		cost = 0
		size = len(arr)
		visited = [False] * size
		visited[0] = True
		same = collections.defaultdict(list)
		for (p, n) in enumerate(arr):
			same[n].append(p)
		st = [0]
		cost = 0
		while True:
			nxt = []
			cost += 1
			while st:
				cur = st.pop()
				for nei in same[arr[cur]] + [cur - 1, cur + 1]:
					if nei == cur or not 0 <= nei < size:
						continue
					if nei == size - 1:
						return cost
					if not visited[nei]:
						visited[nei] = True
						nxt.append(nei)
			st = nxt


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		x = []
		x.append(arr[0])
		for i in range(1, len(arr) - 1):
			if arr[i] == arr[i - 1] and arr[i] == arr[i + 1]:
				continue
			else:
				x.append(arr[i])
		if len(arr) > 1:
			x.append(arr[-1])
		arr = x
		d = collections.defaultdict(list)
		for i in range(len(arr)):
			d[arr[i]].append(i)
		bfs = [0]
		steps = 0
		temp = []
		seen = set([0])
		while len(bfs) > 0:
			index = bfs.pop()
			if index == len(arr) - 1:
				return steps
			if index + 1 < len(arr) and index + 1 not in seen:
				temp.append(index + 1)
				seen.add(index + 1)
			if index - 1 >= 0 and index - 1 not in seen:
				temp.append(index - 1)
				seen.add(index - 1)
			for i in d[arr[index]]:
				if i not in seen:
					temp.append(i)
					seen.add(i)
			if len(bfs) == 0:
				bfs = temp
				temp = []
				steps += 1
		return steps


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		pos = defaultdict(list)
		for (i, num) in enumerate(arr):
			pos[num].append(i)
		(q, steps) = (deque([0]), 0)
		seen = [False] * n
		seen[0] = True
		while q:
			size = len(q)
			for _ in range(size):
				i = q.popleft()
				if i == n - 1:
					return steps
				if i + 1 < n and (not seen[i + 1]):
					q.append(i + 1)
					seen[i + 1] = True
				if i - 1 > -1 and (not seen[i - 1]):
					q.append(i - 1)
					seen[i - 1] = True
				for j in pos[arr[i]]:
					if not seen[j]:
						q.append(j)
						seen[j] = True
				pos[arr[i]].clear()
			steps += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n == 1:
			return 0
		if n == 2:
			return 1
		arr_f = []
		prev = None
		repeat = 0
		for num in arr:
			if num == prev:
				if repeat == 2:
					continue
				repeat += 1
			else:
				prev = num
				repeat = 0
			arr_f.append(num)
		n = len(arr_f)
		idx_by_num = defaultdict(list)
		for i in range(n):
			idx_by_num[arr_f[i]].append(i)
		q = [(0, n - 1)]
		visited = set([n - 1])
		while q:
			(step, cidx) = q.pop(0)
			if cidx == 0:
				return step
			if cidx - 1 not in visited:
				visited.add(cidx - 1)
				q.append((step + 1, cidx - 1))
			if cidx + 1 < n and cidx + 1 not in visited:
				visited.add(cidx + 1)
				q.append((step + 1, cidx + 1))
			for same_v_idx in idx_by_num[arr_f[cidx]]:
				if same_v_idx not in visited:
					visited.add(same_v_idx)
					q.append((step + 1, same_v_idx))


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		graph = collections.defaultdict(list)
		for (i, val) in enumerate(arr):
			graph[val].append(i)

		def dfs():
			queue = deque()
			queue.append((0, 0))
			seen = {0}
			while queue:
				(i, d) = queue.popleft()
				if i == len(arr) - 1:
					return d
				for j in [i - 1, i + 1] + graph[arr[i]][::-1]:
					if 0 <= j < len(arr) and j not in seen and (j != i):
						seen.add(j)
						if j == len(arr) - 1:
							return d + 1
						queue.append((j, d + 1))
		return dfs()


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		bfs = []
		heapq.heappush(bfs, (0, 0))
		seen = {}
		seen[0] = 0
		G = defaultdict(list)
		for (i, a) in enumerate(arr):
			G[a].append(i)
		while bfs:
			(step, idx) = heapq.heappop(bfs)
			idx = -idx
			for d in (-1, 1):
				nidx = idx + d
				if nidx >= 0 and nidx < len(arr):
					if nidx not in seen or seen[nidx] > step + 1:
						if nidx == len(arr) - 1:
							return step + 1
						seen[nidx] = step + 1
						heapq.heappush(bfs, (step + 1, -nidx))
			for d in G[arr[idx]][::-1]:
				if d not in seen or seen[d] > step + 1:
					if d == len(arr) - 1:
						return step + 1
					seen[d] = step + 1
					heapq.heappush(bfs, (step + 1, -d))
		return -1


from collections import defaultdict, deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		mapping = defaultdict(list)
		for (idx, val) in enumerate(arr):
			mapping[val].append(idx)
		visited = set()
		que = deque()
		que.append((0, 0))
		visited.add(0)
		m = len(arr)
		while que:
			top = que.popleft()
			(idx, depth) = (top[0], top[1])
			if idx + 1 < m and idx + 1 not in visited:
				if idx + 1 == m - 1:
					return depth + 1
				visited.add(idx + 1)
				que.append((idx + 1, depth + 1))
			if idx - 1 >= 0 and idx - 1 not in visited:
				visited.add(idx - 1)
				que.append((idx - 1, depth + 1))
			for neigh in mapping[arr[idx]]:
				if neigh not in visited:
					if neigh == m - 1:
						return depth + 1
					visited.add(neigh)
					que.append((neigh, depth + 1))
			mapping.pop(arr[idx])
		return -1


from collections import *

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		mapper = defaultdict(set)
		for (i, x) in enumerate(arr):
			mapper[x].add(i)
		end = len(arr) - 1
		queue = deque([(arr[0], 0, 0)])
		vis = set()
		vis.add(0)
		while queue:
			(num, index, count) = queue.popleft()
			if index == end:
				return count
			if num in mapper:
				for y in mapper.pop(num):
					if y not in vis:
						queue.append((arr[y], y, count + 1))
						vis.add(y)
			if index + 1 <= end and index + 1 not in vis:
				queue.append((arr[index + 1], index + 1, count + 1))
				vis.add(index + 1)
			if index - 1 >= 0 and index - 1 not in vis:
				queue.append((arr[index - 1], index - 1, count + 1))
				vis.add(index - 1)


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if not arr:
			return 0
		valueIndex = collections.defaultdict(list)
		for (i, a) in enumerate(arr):
			valueIndex[a].append(i)
		queue = collections.deque([0])
		visited = {0: 0}
		visitedValues = set()
		while queue:
			head = queue.popleft()
			if head == len(arr) - 1:
				return visited[head]
			shortNeighbor = [head - 1, head + 1]
			for neighbor in shortNeighbor:
				if 0 <= neighbor < len(arr) and (not neighbor in visited):
					visited[neighbor] = visited[head] + 1
					queue.append(neighbor)
			if arr[head] not in visitedValues:
				visitedValues.add(arr[head])
				for neighbor in valueIndex[arr[head]]:
					if neighbor not in visited:
						visited[neighbor] = visited[head] + 1
						queue.append(neighbor)
		return visited[len(arr) - 1]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		q = deque([[0, 0]])
		d = defaultdict(list)
		vis = set([0])
		for (i, val) in enumerate(arr):
			d[val].append(i)
		while q:
			(idx, steps) = q.popleft()
			if idx == len(arr) - 1:
				return steps
			for i in d.pop(arr[idx], []) + [idx + 1, idx - 1]:
				if i not in vis and i >= 0:
					vis.add(i)
					q.append([i, steps + 1])


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		q = collections.deque()
		seen = set()
		hashmap = collections.defaultdict(list)
		destination = len(arr) - 1
		minJumps = 0
		for (index, num) in enumerate(arr):
			hashmap[num].append(index)
		q.append(0)
		seen.add(0)
		while q:
			sizeQ = len(q)
			for i in range(sizeQ):
				Pos = q.popleft()
				if Pos == destination:
					return minJumps
				nextPos = Pos + 1
				prevPos = Pos - 1
				mirrorPos = hashmap[arr[Pos]]
				if nextPos >= 0 and nextPos < len(arr) and (nextPos not in seen):
					seen.add(nextPos)
					q.append(nextPos)
				if prevPos >= 0 and prevPos < len(arr) and (prevPos not in seen):
					seen.add(prevPos)
					q.append(prevPos)
				if mirrorPos:
					for val in mirrorPos:
						if val >= 0 and val < len(arr) and (val not in seen):
							seen.add(val)
							q.append(val)
					del hashmap[arr[Pos]]
			minJumps += 1
		return minJumps


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		bfs = [0]
		seen = set()
		seen.add(0)
		G = defaultdict(list)
		for (i, a) in enumerate(arr):
			G[a].append(i)
		step = 0
		while bfs:
			(cur, bfs) = (bfs, [])
			for idx in cur:
				if idx == len(arr) - 1:
					return step
				for d in (-1, 1):
					nidx = idx + d
					if nidx >= 0 and nidx < len(arr):
						if nidx not in seen:
							seen.add(nidx)
							bfs.append(nidx)
				for d in G[arr[idx]]:
					if d not in seen:
						if d not in seen:
							seen.add(d)
							bfs.append(d)
				G.pop(arr[idx])
			step += 1
		return -1


from collections import defaultdict
from heapq import heappush, heappop

class Solution:

	def adjacent(self, arr, i, jumps):
		if i > 0:
			yield (i - 1)
		if i < len(arr) - 1:
			yield (i + 1)
		for j in jumps[arr[i]]:
			if i != j:
				yield j

	def minJumps(self, arr: List[int]) -> int:
		if not arr:
			return 0
		jumps = defaultdict(set)
		for (i, v) in enumerate(arr):
			if i == 0 or i == len(arr) - 1 or arr[i - 1] != v or (arr[i + 1] != v):
				jumps[v].add(i)
		steps = {}
		pq = []
		heappush(pq, (0, 0))
		while pq:
			(n, neg_i) = heappop(pq)
			i = -neg_i
			if i == len(arr) - 1:
				return n
			for j in self.adjacent(arr, i, jumps):
				if j not in steps or steps[j] > n + 1:
					steps[j] = n + 1
					heappush(pq, (n + 1, -j))


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		from collections import deque, defaultdict
		d = defaultdict(set)
		q = deque([0])
		res = 0
		last = len(arr) - 1
		for i in range(len(arr)):
			d[arr[i]].add(i)
		d[arr[0]].remove(0)
		print(d)
		while q:
			for i in range(len(q)):
				e = q.popleft()
				if e == last:
					return res
				if e - 1 >= 0 and e - 1 in d[arr[e - 1]]:
					q.append(e - 1)
					d[arr[e - 1]].remove(e - 1)
				if e + 1 <= last and e + 1 in d[arr[e + 1]]:
					q.append(e + 1)
					d[arr[e + 1]].remove(e + 1)
				for n in d[arr[e]]:
					q.append(n)
				d[arr[e]] = []
			res += 1
		return res


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		lim = len(arr)
		d = dict()
		for i in range(0, lim):
			if arr[i] in d:
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		for x in d:
			d[x].sort(reverse=True)
		start = []
		a = [-1 for i in range(0, lim)]
		start = [[0, 0]]
		for x in d[arr[0]]:
			if x != 0:
				start.append([x, 1])
				a[x] = 1
		start.sort(key=lambda x: x[1])
		while 1 != -1:
			tmp = []
			for x in start:
				if x[0] == lim - 1:
					return x[1]
				if x[0] + 1 == lim - 1:
					return x[1] + 1
				a[x[0]] = 1
				if x[0] > 0 and a[x[0] - 1] == -1:
					tmp.append([x[0] - 1, x[1] + 1])
				if a[x[0] + 1] == -1:
					tmp.append([x[0] + 1, x[1] + 1])
				for y in d[arr[x[0]]]:
					if a[y] == -1:
						tmp.append([y, x[1] + 1])
			start = tmp


from collections import deque
from collections import defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return 0
		d = defaultdict(list)
		for (i, num) in enumerate(arr):
			d[num].append(i)
		length = len(arr)
		q = deque()
		level = 0
		q.append(0)
		s = set()
		s.add(0)
		while len(q) > 0:
			size = len(q)
			while size > 0:
				top = q.popleft()
				if top - 1 >= 0 and top - 1 not in s:
					s.add(top - 1)
					q.append(top - 1)
				if top + 1 < length and top + 1 not in s:
					if top + 1 == length - 1:
						return level + 1
					s.add(top + 1)
					q.append(top + 1)
				for i in range(len(d[arr[top]])):
					idx = d[arr[top]][len(d[arr[top]]) - 1 - i]
					if idx not in s:
						if idx == length - 1:
							return level + 1
						q.append(idx)
						s.add(idx)
				size -= 1
			level += 1
		return level


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		m = len(arr)
		seen = [False for _ in range(m)]
		q = deque()
		step = 0
		quick_jump_graph = {}
		for i in range(len(arr)):
			if arr[i] in quick_jump_graph:
				quick_jump_graph[arr[i]].append(i)
			else:
				quick_jump_graph[arr[i]] = [i]
		q.append(0)
		while len(q):
			s = len(q)
			for i in range(s):
				cur_idx = q.popleft()
				if cur_idx < 0 or cur_idx >= m or seen[cur_idx]:
					continue
				elif cur_idx == m - 1:
					return step
				else:
					seen[cur_idx] = True
					q.append(cur_idx + 1)
					q.append(cur_idx - 1)
					if len(quick_jump_graph[arr[cur_idx]]) != 0:
						for num in quick_jump_graph[arr[cur_idx]]:
							q.append(num)
						quick_jump_graph[arr[cur_idx]] = []
			step += 1
		return -1


class Solution:

	def minJumps_tle(self, arr: List[int]) -> int:
		if not arr:
			return 0
		(visited, L, lookup) = (set(), len(arr), collections.defaultdict(list))
		que = collections.deque()
		que.append((0, 0))
		visited.add(0)
		for (k, v) in enumerate(arr):
			lookup[v].append(k)
		while que:
			(c, s) = que.popleft()
			if c == L - 1:
				return s
			if c + 1 not in visited and c + 1 < L:
				visited.add(c + 1)
				que.append((c + 1, s + 1))
			if L > c - 1 >= 0 and c - 1 not in visited:
				visited.add(c - 1)
				que.append((c - 1, s + 1))
			for i in lookup[arr[c]]:
				if i == c:
					continue
				if i not in visited and 0 <= i < L:
					visited.add(i)
					que.append((i, s + 1))
		return -1

	def minJumps(self, arr: List[int]) -> int:
		if not arr:
			return 0
		(visited, L, lookup) = (set(), len(arr), collections.defaultdict(list))
		que = collections.deque()
		que.append(0)
		visited.add(0)
		for (k, v) in enumerate(arr):
			lookup[v].append(k)
		step = 0
		while que:
			size = len(que)
			for i in range(size):
				c = que.popleft()
				if c == L - 1:
					return step
				if c + 1 not in visited and 0 <= c + 1 < L:
					visited.add(c + 1)
					que.append(c + 1)
				if L > c - 1 >= 0 and c - 1 not in visited:
					visited.add(c - 1)
					que.append(c - 1)
				for i in lookup[arr[c]]:
					if i == c:
						continue
					if i not in visited and 0 <= i < L:
						visited.add(i)
						que.append(i)
				del lookup[arr[c]]
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		mirrors = collections.defaultdict(list)
		_ = [mirrors[x].append(i) for (i, x) in enumerate(arr)]
		visited = set()
		q = collections.deque([(0, 0)])
		while q:
			(idx, jump) = q.popleft()
			if idx == n - 1:
				return jump
			for nei in [idx - 1, idx + 1] + mirrors[arr[idx]]:
				if 0 <= nei < n and nei not in visited:
					visited.add(nei)
					q.append((nei, jump + 1))
			del mirrors[arr[idx]]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		visited = {0}
		lookup = defaultdict(list)
		for (i, val) in enumerate(arr):
			lookup[val].append(i)
		deq = deque([(0, 0)])
		while deq:
			(i, step) = deq.popleft()
			if i == len(arr) - 1:
				return step
			nxt_idx = [i - 1, i + 1]
			nxt_idx.extend(lookup[arr[i]])
			lookup[arr[i]] = []
			for nxt in nxt_idx:
				if 0 <= nxt < len(arr) and nxt not in visited:
					deq.append((nxt, step + 1))
					visited.add(nxt)
		return 0


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		graph = defaultdict(list)
		for i in range(len(arr)):
			graph[arr[i]].append(i)
		visited = set()
		(src, dest) = (0, len(arr) - 1)
		queue = deque()
		queue.append((src, 0))
		visited.add(src)
		while queue:
			(vid, step) = queue.popleft()
			if vid == dest:
				return step
			nextLayer = [vid - 1, vid + 1] + graph[arr[vid]]
			for v in nextLayer:
				if 0 <= v < len(arr) and v != vid and (v not in visited):
					visited.add(v)
					queue.append((v, step + 1))
			del graph[arr[vid]]
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		idxs = defaultdict(list)
		for (i, v) in enumerate(arr):
			if 0 < i < n - 1 and arr[i - 1] == v == arr[i + 1]:
				continue
			idxs[v].append(i)
		q = deque([(0, 0)])
		visited = set()
		while q:
			(i, cnt) = q.popleft()
			visited.add(i)
			if i == len(arr) - 1:
				return cnt
			for j in [i - 1, i + 1]:
				if 0 <= j < n and j not in visited:
					q.append((j, cnt + 1))
			for j in idxs[arr[i]]:
				if j != i and j not in visited:
					q.append((j, cnt + 1))
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		dict1 = {}
		i = 0
		n = len(arr)
		while i < n:
			if arr[i] in dict1:
				dict1[arr[i]].append(i)
			else:
				dict1[arr[i]] = [i]
			cur = arr[i]
			j = 1
			while i + j < n:
				if arr[i + j] == cur:
					j += 1
				else:
					break
			if j > 1:
				dict1[arr[i]].append(i + j - 1)
			i += j
		curPoss = {0}
		cnt = 0
		while curPoss != []:
			nextPoss = set()
			for cur in curPoss:
				if cur == n - 1:
					return cnt
				l = cur - 1
				if 0 < l < n and l not in curPoss and (arr[l] != None):
					nextPoss.add(l)
				r = cur + 1
				if 0 < r < n and r not in curPoss and (arr[r] != None):
					nextPoss.add(r)
				for i in dict1[arr[cur]]:
					if i != cur and i not in curPoss and (arr[i] != None):
						nextPoss.add(i)
				arr[cur] = None
			curPoss = nextPoss
			cnt += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		queue = deque([0])
		visited = set([0])
		map = defaultdict(list)
		for (idx, num) in enumerate(arr):
			map[num].append(idx)
		step = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				pos = queue.popleft()
				if pos == len(arr) - 1:
					return step
				for nxt in [pos - 1, pos + 1]:
					if nxt < 0 or nxt >= len(arr) or nxt in visited:
						continue
					queue.append(nxt)
					visited.add(nxt)
				for neighbor in map[arr[pos]]:
					if neighbor not in visited:
						queue.append(neighbor)
						visited.add(neighbor)
				del map[arr[pos]]
			step += 1
		return -1


from collections import deque, defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		idxs = defaultdict(list)
		for (idx, e) in enumerate(arr):
			idxs[e].append(idx)

		def bfs(idx):
			q = deque([0])
			step = -1
			not_visited = set(range(len(arr) - 1, 0, -1))
			while q:
				step += 1
				for _ in range(len(q)):
					node = q.popleft()
					if node == len(arr) - 1:
						return step
					nxt_nodes = set(idxs[arr[node]] + [node + 1, node - 1])
					nxt_nodes = not_visited & nxt_nodes
					if len(arr) - 1 in nxt_nodes:
						return step + 1
					not_visited.difference_update(nxt_nodes)
					nxt_nodes = sorted(nxt_nodes, reverse=True)
					q.extend(nxt_nodes)
			return -1
		return bfs(0)


from collections import defaultdict, deque

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		node_h = defaultdict(list)
		graph = defaultdict(set)
		for (idx, val) in enumerate(arr):
			node_h[val].append(idx)
		q = deque()
		visited = set()
		q.append((0, 0))
		visited.add(0)
		while q:
			(node, level) = q.popleft()
			if node == len(arr) - 1:
				return level
			nbrs = node_h[arr[node]]
			nbrs.append(node - 1)
			nbrs.append(node + 1)
			for nbr in nbrs:
				if nbr == len(arr) - 1:
					return level + 1
				if nbr >= 0 and nbr < len(arr) and (nbr not in visited):
					q.append((nbr, level + 1))
					visited.add(nbr)
			node_h[arr[node]] = []
		return 0


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		from collections import defaultdict, deque
		n = len(arr)
		indices = defaultdict(list)
		for i in range(n):
			indices[arr[i]].append(i)
		visited = [False] * n
		visited[0] = True
		queue = deque()
		queue.append(0)
		steps = 0
		while len(queue) > 0:
			for size in range(len(queue), 0, -1):
				i = queue.popleft()
				if i == n - 1:
					return steps
				next = indices[arr[i]]
				next.append(i - 1)
				next.append(i + 1)
				for num in next:
					if num >= 0 and num < n and (not visited[num]):
						visited[num] = True
						queue.append(num)
				indices[arr[i]] = []
			steps += 1
		return 0


from collections import deque, defaultdict

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		visited = {0}
		q = deque([(0, 0)])
		val_to_is = defaultdict(list)
		for (i, val) in enumerate(arr):
			val_to_is[val].append(i)

		def move(i):
			for j in [i - 1, i + 1] + val_to_is[arr[i]]:
				if 0 <= j < len(arr) and j != i and (j not in visited):
					yield j
		while q:
			(i, steps) = q.pop()
			for j in move(i):
				if j == len(arr) - 1:
					return steps + 1
				visited.add(j)
				if arr[i] in val_to_is:
					del val_to_is[arr[i]]
				q.appendleft((j, steps + 1))
		return 0


from queue import Queue

def dedup(arr):
	n = len(arr)
	if n <= 2:
		return arr
	ret = [arr[0]]
	is_equal = False
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			if not is_equal:
				is_equal = True
				ret.append(arr[i])
			else:
				ret[-1] = arr[i]
		else:
			ret.append(arr[i])
			is_equal = False
	return ret

class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if len(set(arr)) == len(arr):
			return len(arr) - 1
		arr = dedup(arr)
		memo = defaultdict(list)
		n = len(arr)
		visited = [0] * n
		for i in range(n):
			memo[arr[i]].append(i)
		q = Queue()
		q.put((0, 0))
		visited[0] = 1
		while not q.empty():
			(cur, cnt) = q.get()
			if cur == n - 1:
				return cnt
			wk = [cur + 1, cur - 1]
			for v in memo[arr[cur]] + wk:
				if -1 < v < n and (not visited[v]):
					q.put((v, cnt + 1))
					visited[v] = 1
		return 0


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		dp = {}
		count = {}
		for i in range(len(arr)):
			res = count.get(arr[i], [])
			res.append(i)
			count[arr[i]] = res
		vis = set()
		vis.add(0)
		q = collections.deque([(0, 0)])
		c = 0
		while q:
			l = len(q)
			for i in range(l):
				node = q.popleft()
				if node[0] == len(arr) - 1:
					return node[1]
				if node[0] != 0:
					if node[0] - 1 not in vis:
						q.append((node[0] - 1, node[1] + 1))
						vis.add(node[0] - 1)
				if node[0] != len(arr) - 1:
					if node[0] + 1 not in vis:
						q.append((node[0] + 1, node[1] + 1))
						vis.add(node[0] + 1)
				for j in count[arr[node[0]]]:
					if j not in vis and j != node[0]:
						q.append((j, node[1] + 1))
						vis.add(j)
				if j in count[arr[node[0]]]:
					count[arr[node[0]]] = []
			c += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		indexes = collections.defaultdict(list)
		for (idx, v) in enumerate(arr):
			indexes[v].append(idx)
		for key in indexes:
			indexes[key] = [v for (j, v) in enumerate(indexes[key]) if not (1 <= j < len(indexes[key]) - 1 and indexes[key][j - 1] == v - 1 and (indexes[key][j + 1] == v + 1))]
		(queue, visited) = (collections.deque([(0, 0)]), set([0]))
		while queue:
			(idx, jumps) = queue.popleft()
			if idx == len(arr) - 1:
				return jumps
			v = arr[idx]
			for j in [idx + 1, idx - 1] + indexes[v][::-1]:
				if 0 <= j < len(arr) and j not in visited:
					visited.add(j)
					queue.append((j, jumps + 1))


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		map = defaultdict(list)
		for (i, item) in enumerate(arr):
			map[item].append(i)
		q = deque()
		q.appendleft((0, 0))
		visited = set()
		num_vis = set()
		while q:
			(index, jumps) = q.pop()
			if index == len(arr) - 1:
				return jumps
			visited.add(index)
			if arr[index] not in num_vis:
				nxts = map[arr[index]]
				num_vis.add(arr[index])
				for nxt in nxts:
					if nxt < 0 or nxt > len(arr) or nxt in visited:
						continue
					q.appendleft((nxt, jumps + 1))
			for nbr in [index + 1, index - 1]:
				if nbr < 0 or nbr >= len(arr) or nbr in visited:
					continue
				q.appendleft((nbr, jumps + 1))
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if not arr or len(arr) == 1:
			return 0
		n = len(arr)
		same_val = {}
		for i in range(n):
			if arr[i] not in same_val:
				same_val[arr[i]] = [i]
			else:
				same_val[arr[i]].append(i)
		visited = [False] * n
		step = 0
		curr = [0]
		while curr:
			next = []
			for i in curr:
				if i == n - 1:
					return step
				visited[i] = True
				for next_idx in same_val[arr[i]]:
					if not visited[next_idx]:
						next.append(next_idx)
				same_val[arr[i]].clear()
				for next_idx in [i - 1, i + 1]:
					if 0 <= next_idx < n and (not visited[next_idx]):
						next.append(next_idx)
			curr = next
			step += 1
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		if not arr:
			return 0
		n = len(arr)
		val_to_pos = collections.defaultdict(list)
		for (i, val) in enumerate(arr):
			val_to_pos[val].append(i)
		dist = 0
		curr_set = set([0])
		other_set = set([n - 1])
		curr_visited = curr_set
		other_visited = other_set
		while curr_set and other_set:
			if len(other_set) < len(curr_set):
				(curr_set, other_set) = (other_set, curr_set)
				(curr_visited, other_visited) = (other_visited, curr_visited)
			next_set = set()
			while curr_set:
				curr = curr_set.pop()
				if curr in other_visited:
					return dist
				for nei in val_to_pos[arr[curr]] + [curr + 1, curr - 1]:
					if not 0 <= nei < n:
						continue
					if nei in curr_visited:
						continue
					next_set.add(nei)
				val_to_pos[arr[curr]] = []
			curr_visited |= next_set
			curr_set = next_set
			dist += 1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 1:
			return 0
		dictor = collections.defaultdict(list)
		queue = collections.deque([(0, 0)])
		for i in range(n):
			dictor[arr[i]].append(i)
		seen = set([0, n - 1])
		while queue:
			(idx, step) = queue.popleft()
			indexes = dictor[arr[idx]]
			for i in indexes:
				if i == n - 1:
					return step + 1
				if i not in seen:
					queue.append((i, step + 1))
					seen.add(i)
			del dictor[arr[idx]]
			for di in [-1, 1]:
				new_i = idx + di
				if new_i == n - 1:
					return step + 1
				if 0 <= new_i < len(arr) and new_i not in seen:
					queue.append((new_i, step + 1))
					seen.add(new_i)
		return -1


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		g = defaultdict(list)
		for (i, v) in enumerate(arr):
			g[v].append(i)
		N = len(arr)
		val_flag = set()
		cost = [math.inf] * N
		cost[0] = 0
		heap = [(0, 0)]
		while heap:
			(c, i) = heappop(heap)
			if i == N - 1:
				return c
			for n in g[arr[i]] * (arr[i] not in val_flag) + [i - 1, i + 1]:
				if not 0 <= n < N:
					continue
				if cost[n] > c + 1:
					cost[n] = c + 1
					heappush(heap, (c + 1, n))
			val_flag.add(arr[i])
		return cost[-1]


class Solution:

	def minJumps(self, arr: List[int]) -> int:
		pos = {}
		for (i, x) in enumerate(arr):
			if x in pos:
				pos[x][0].append(i)
			else:
				pos[x] = [[i], False]
		q = deque([(len(arr) - 1, 0, True), (0, 0, False)])
		visited = [[-1, -1] for _ in range(len(arr))]
		while q:
			(i, n, d) = q.popleft()
			if visited[i][int(not d)] != -1:
				return n + visited[i][int(not d)]
			if visited[i][int(d)] != -1:
				continue
			visited[i][int(d)] = n
			if i < len(arr) - 1:
				q.append((i + 1, n + 1, d))
			if i > 0:
				q.append((i - 1, n + 1, d))
			if not pos[arr[i]][1]:
				for idx in pos[arr[i]][0]:
					q.append((idx, n + 1, d))
				pos[arr[i]][1] = True