Конрад — консультант по человеческим отношениям, работающий в VoltModder, крупном производителе электрооборудования. Сегодня ему было поручено оценить уровень счастья в компании.
В VoltModder работает \(n\) человек, пронумерованных от \(1\) до \(n\). Каждый работник зарабатывает разное число денег — изначально, \(i\)-й человек зарабатывает \(i\) рублей в день.
В каждый из \(q\) следующих дней, зарплаты будут пересмотрены. В конце \(i\)-го дня работник \(v_i\) начнет получать \(n+i\) рублей в день и станет самым оплачиваемым работником в компании. Его зарплата будет оставаться такой же до её следующего пересмотра.
Некоторые пары людей не любят друг друга. Это создает в компании большое психологическое напряжение. Формально, если два человека \(a\) и \(b\) не любят друга друга, и \(a\) зарабатывает больше денег, чем \(b\), работник \(a\) похвастается этим \(b\). Опасная тройка это тройка из трех таких работников \(a\), \(b\) и \(c\), что \(a\) похвастается \(b\), который, в свою очередь, похвастается \(c\). Если \(a\) не любит \(b\), то и \(b\) не любит \(a\).
В начале каждого дня, Конрад должен посчитать количество опасных троек в компании. Можете ли вы ему помочь в этом?
Примечание
Рассмотрим первый пример. \(i\)-я строка в следующей иллюстрации показывает структуру компании в \(i\)-й день. Ориентированное ребро из \(a\) в \(b\) описывает, что работник \(a\) похвастается работнику \(b\). Опасные тройки показаны подсвеченными ребрами.
