oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

sorting_codechef Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

sorting.html

Sorting

Alice uses the following pseudocode when she needs to sort a permutation of 1 to N in a 1-indexed array:

procedure Sort(list A) defined as: 
   list less, greater
   if length(A) <= 1 then return A
   pivot := Afloor((length(A)+1) / 2)
   for i := 1 to length(A) do:
      Increment(comparison_count)
      if Ai < pivot then append Ai to less else if Ai > pivot append Ai to greater
      end if
   end for
   return concatenate(Sort(less), pivot, Sort(greater) )

And now we are interested in the number of comparisons that will be made during the sorting of the given permutation of integers A with the provided code. So, we ask you to find the value of the variable comparison_count after such a sorting.

Input

The first line of input consists of a single integer N. The second line of input contains a permutation of the numbers 1 to N.

Output

Output the number of comparisons on the first and only line of the output.

Limits

For all testcases

  • 1 ≤ N ≤ 500000

Subtask 1 (32%): 1 ≤ N ≤ 2000

Subtask 2 (9%): 1 ≤ N ≤ 100000, the permutation is generated randomly

Subtask 3 (45%): 1 ≤ N ≤ 65536

Subtask 4 (14%): No additional constraints

Subtask 5 (0%): Sample

Sample Input

5
4 3 5 1 2

Sample Output

11

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13292.5s512MBMinimum
2942.5s512MBMinimum
34592.5s512MBMinimum
41492.5s512MBMinimum
5012.5s512MBMinimum

Judge Compile Command

g++-8 ans.cpp -o sorting_codechef -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.