Артур Числовский получил на свой день рождения массив из
N целых чисел в подарок. Но ему он не понравился. Артур Числовский хочет сделать этот массив красивым. Числовский считает массив
A1,
A2,
A3 ...
AN красивым, если
A1 >
AN. Чтобы сделать его красивым, Артур Числовский может поменять местами любые два числа в массиве. Кроме того, Артур Числовский может выполнять эту операцию любое количество раз над смежными парами целых чисел в массиве
A. Найдите количество способов, которыми Артур Числовский может сделать этот массив красивым. Два способа считаются одинаковыми, если итоговый массив после всех обменов имеет одинаковые значения
A1 и
AN.
Формат входных данных
Первая строка ввода содержит целое число N, обозначающее количество элементов в массиве A. Следующая строка ввода содержит N разделенных пробелом целых чисел, обозначающих A1,A2,A3 ... AN соответственно.
Ограничения
1 ≤ N ≤ 106
1 ≤ Ai ≤ 106
Формат выходных данных
Выведите одно число - количество способов, с помощью которых можно сделать данный массив красивым.
Примечание
В приведенном примере общее количество способов равно (5,1),(4,1),(3,1),(2,1),(5,2),(4,2),(3,2),(5,3),(4,3),(5,4). Первое число в приведенной выше паре - A[1], а второе - A[N]. Заметим, что два способа считаются одинаковыми, если A[1] и A[N] в результирующем массиве после обмена совпадают.
Запрещенные операторы: set
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4 3 2 5
|
10
|