Codeforces Round 305 (Div. 1) |
---|
Закончено |
Майк — бармен в баре Рико. В заведении Рико пивные стаканы кладутся на особую полку. Всего в баре n сортов пива, пронумерованных от 1 до n. Бокал с i-м сортом пива содержит ai миллилитров пены.
Максим — босс Майка. Сегодня он сказал Майку выполнить q запросов. Изначально полка пустая. Каждый запрос представляет собой целое число x. Если пиво номер x уже есть на полке, то Майк должен забрать его с полки, в противном случае — положить его на полку.
После каждого запроса Майк должен определить качество полки. Медведи — те ещё гики, так что они считают, что качество полки — это количество пар (i, j) стаканов на полке, таких, что i < j и , где — наибольший общий делитель чисел a и b.
Майк устал. Поэтому он попросил вам помочь ему выполнить эти запросы.
В первой строке ввода записаны числа n и q (1 ≤ n, q ≤ 2 × 105), количество различных видов пива и количество запросов.
В следующей строке записано n целых чисел через пробел, a1, a2, ... , an (1 ≤ ai ≤ 5 × 105), высота пены на каждом сорте пива.
В следующих q строках записаны запросы. Каждый запрос состоит из единственного целого числа x (1 ≤ x ≤ n), — номера сорта пива, которое надо добавить на полку или убрать оттуда.
Для каждого запроса выведите ответ в отдельной строке.
5 6
1 2 3 4 6
1
2
3
4
5
1
0
1
3
5
6
2
Название |
---|