Фермер Джон устраивает турнир по теннису среди своих n коровок. У каждой коровки есть умение s_i, и никакие две коровки не обладают одинаковым умением. На протяжении турнира, каждая коровка играет с каждой другой коровкой ровно один раз, в таком поединке коровка с большим умением побеждает коровку с меньшим умением.

Однако Фермер Джон беспокоится, что турнир уничтожит самооценку самых слабых коровок, которые проиграют большую часть своих матчей... И вот он решил немного поменять результаты. Ровно k раз он возьмет два целых числа a_i, b_i (a_i < b_i) и поменяет все результаты матчей коровок с умениями от a_i до b_i, включительно. Таким образом, для каждой пары x, y он поменяет результат матча между коровками x и y (то есть, если матч выиграла x, то после изменения будет считаться, что победила y и наоборот). Возможно, Фермер Джон поменяет результат какого-то одного матча несколько раз. Обратите внимание, что a_i и b_i могут быть не равны умению той или иной коровки.

Фермер Джон хочет вычислить, насколько сбалансированными будут результаты турнира. Для этого он хочет посчитать количество троек коровок (p, q, r), для которых в итоге будет считаться, что коровка p выиграла у коровки q, коровка q выиграла у коровки r, а коровка r выиграла у коровки p. Помоги ему вычислить это количество.

Обратите внимание, что две тройки считаются различными тогда, когда они не содержат одинаковый набор коровок (то есть, некоторая коровка есть в одной тройке и отсутствует в другой).