Майк — бармен в баре Рико. В заведении Рико пивные стаканы кладутся на особую полку. Всего в баре n сортов пива, пронумерованных от 1 до n. Бокал с i-м сортом пива содержит ai миллилитров пены.
Максим — босс Майка. Сегодня он сказал Майку выполнить q запросов. Изначально полка пустая. Каждый запрос представляет собой целое число x. Если пиво номер x уже есть на полке, то Майк должен забрать его с полки, в противном случае — положить его на полку.
После каждого запроса Майк должен определить качество полки. Медведи — те ещё гики, так что они считают, что качество полки — это количество пар (i, j) стаканов на полке, таких, что i < j и
, где
— наибольший общий делитель чисел a и b.
Майк устал. Поэтому он попросил вам помочь ему выполнить эти запросы.