21/11/2024 20:17:28

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1831. Sorting

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Consider the following sorting algorithm:

reverse-sort(sequence a) 
       while (a is not in nondecreasing order) 
               partition a into the minimum number of slopes 
               for every slope with length greater than one 
                       reverse(slope)

A slope is defined as a decreasing consecutive subsequence of `a`. The reverse procedure will reverse the order of the elements in a slope.

You are given a permutation of the first `N` natural numbers whose slopes all have even length when partitioned for the first time. Determine the total number of times reverse is called to reverse-sort the given permutation.

The first line of input contains the positive integer `N` (`2\ ≤\ N\ ≤\ 100\ 000`). The second line of input contains a permutation of the first `N` natural numbers that needs to be sorted.

The only line of output must contain the number of times that reverse is called.

Sample Input #1

2 
2 1

Sample Output #1

Sample Input #2

4 
4 3 2 1

Sample Output #2

Sample Input #3

4 
3 1 4 2

Sample Output #3

Source: COCI 2011/2012

25/06/2012	Лето 2012 - дорешивание (13E)
13/07/2012	Лето 2012 - 13 (E)