Із сортування (Платина)

Бесі створила гібрид двох своїх улюблених алгоритмів: бульбашкового сортування та швидкого сортування. Вона називає позицію між елементами i та i + 1 масиву A точкою розбиття, якщо максимум з A[...i] не перевищує мінімум A[i + 1...]. Бесі пам'ятає, що швидке сортування реорганізує масив так, щоб з'явилася точка розбиття, а потім рекурсивно сортує частини A[...i] та A[i + 1...]. Проте, вона забула, як у швидкому сортуванні реорганізується масив для швидкого створення точки розбиття. Тому вона вирішила використати бульбашкове сортування для цього завдання.

Ось алгоритм Бесі. Спочатку вона написала просту функцію, яка виконує один прохід бульбашкового сортування:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Рекурсивний код Бесі для "швидкого" сортування виглядає так:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Основний цикл
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A) 
   divide A at all partition points; recursively quickish_sort each piece
}

Тепер Бесі цікаво, наскільки швидко працює її код. Для простоти вона вважає, що її ітерація працює лінійно, тому вона просто збільшує глобальну змінну work_counter всередині циклу на поточний розмір масиву, щоб оцінити загальну роботу, виконану алгоритмом.

За заданим вхідним масивом, передбачте фінальне значення величини work_counter після завершення алгоритму quickish_sort.

Вхідні дані

Перший рядок містить n (1 ≤ n ≤ 10^5). Наступні n рядків описують A[0]..A[n−1], кожен з яких є цілим числом у діапазоні 0..10^9. Не гарантується, що всі елементи різні.

Вихідні дані

Виведіть кінцеве значення величини work_counter.

Приклад

У цьому прикладі ми починаємо з масиву 20 2 3 4 9 8 7. Після одного проходу бульбашкового сортування (додаючи 7 до work counter) ми отримуємо масив 2 | 3 | 4 | 9 8 7 | 20, де символ | позначає точку розбиття. Тому наше завдання розбивається на рекурсивні підзадачі сортування чисел 2, 3, 4, 20 (кожна займає 0 одиниць роботи) та 9 8 7. Для підзадачі 9 8 7 один прохід основного циклу (3 одиниці роботи) будує масив 8 7 | 9, після чого робиться фінальний виклик 8 7 (2 одиниці роботи) і алгоритм завершено.

Приклади