Хоссам дал вам последовательность целых чисел \(a_1, \, a_2, \, \dots, \, a_n\) длины \(n\). Кроме того, он последовательно дает вам \(q\) запросов вида \((l, \, r)\). Для каждого запроса он хочет знать среди чисел \(a_l, \, a_{l + 1}, \, \dots, \, a_r\) такое минимальное число, что оно встречается в заданном отрезке последовательности нечетное количество раз.
Вы должны посчитать ответ на каждый запрос, прежде чем отвечать на следующий.
Выходные данные
Для каждого запроса выведите минимальное число, которое встречается на заданном отрезке последовательности нечетное количество раз.
Если такого числа не существует, выведите \(0\).
Примечание
В данном примере
\(\)l_1 = 1, \, r_1 = 2,\(\) \(\)l_2 = 1, \, r_2 = 3,\(\) \(\)l_3 = 2, \, r_3 = 4,\(\) \(\)l_4 = 1, \, r_4 = 4,\(\) \(\)l_5 = 2, \, r_5 = 2,\(\) \(\)l_6 = 1, \, r_6 = 5.\(\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7
|
1
2
1
0
2
2
|
|
2
|
10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61
|
51
55
19
48
76
19
23
19
55
19
|