Найти элемент с наибольшим расстоянием в данном массиве, где каждый элемент встречается дважды?

Дан массив int, каждый int встречается в нем ровно ДВА раза. найдите и верните такое int, что эта пара int имеет максимальное расстояние между ними в этом массиве.

например, [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2

Мои идеи:

Использовать hashmap, ключ - a[i], значение - индекс. Сканируем a[], каждое число заносим в хэш. Если число встречается дважды, используйте его индекс минус индекс старого числа и используйте результат для обновления значения элемента в хэше.

После этого просканируйте хэш и верните ключ с наибольшим элементом (расстоянием). Это O(n) по времени и пространству.

Как сделать это за O(n) времени и O(1) пространства?