Little Monk and Swaps
Tag(s):

Binary Search Tree, Data Structures, Easy-Medium

Problem
Editorial
Analytics

Given a complete binary tree with N nodes and each node have an distinct integer $a_i$ attached with it, find the minimum number of swaps you can make to convert the binary tree into binary search tree. In one swap, you can select any two nodes and swap their values.

You will be given the array representation of the binary tree. Root of the tree will be at $a_1$. Left child of root will be at $a_2$ and right child of root will be at $a_3$. Left child of node at array position k will be at $a_{2 * k}$ and right child of node at array position k will be at $a_{2 * k + 1}$.

Input format:
First line contains an integer, N $(1 \le N \le 10^5)$, denoting the number of nodes. Second line contains N space separated integers, $a_i$ $(1 \le a_i \le 10^5)$,, denoting the value attached to $i^{th}$ node.

Output format:
Print a single integer, denoting the minimum number of swaps needed to convert binary tree into a binary search tree.

SAMPLE INPUT
3
1 2 3

SAMPLE OUTPUT
1

Explanation

We need to only one swap $(1, 2)$ to convert the given binary tree into binary search tree.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...