C++UCS301
Complexity Lab C++ Setup Visualizer
Practice arena
C++17·2 s·128 MB
SortingFoundation

Count insertion moves

Perform insertion sort and count every right-shift of an element that is greater than the key being inserted. Equal values must keep their relative order.

Input

  • — The first line contains T.
  • — Each case contains n followed by n integers.

Output

Print the number of right-shifts required for each case.

Technique

stable insertion-sort trace

Target

O(n²) worst case · O(1) extra

Constraints & sample
  • 1 ≤ n ≤ 100,000
  • Use a 64-bit counter
  • The judge includes small and moderately sized arrays suitable for insertion-sort tracing

Sample input

3
5
2 4 1 3 5
4
4 3 2 1
5
1 1 1 1 1

Expected output

3
6
0
Review the concept

Before you submit

  • Test the smallest valid input and one awkward edge case.
  • Keep the solution within O(n²) worst case · O(1) extra.
  • Match spacing and line breaks exactly before checking 8 hidden cases.
main.cpp
Draft saved locally · 496 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17

Visible testcases

Editable and stored only in this browser. Hidden judge cases never change.

Checking your session…

Run checks Sample · Submit checks 8 hidden cases

Run the sample first, then send your solution through 8 hidden cases.

Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.