***Veronica Mars and the Binary Search Tree( INDEX AT WHICH A NODE WILL BE INSERT IN THE BST)

Veronica Mars and the Binary Search Tree

With the help of Mac, Veronica Mars just came up with a new way of numbering Binary Search Tree(BST) nodes! She assigns the number 1$1$ to the root node, and any node indexed as i$i$ will have a left child indexed as 2⋅i$2\cdot i$ and a right child indexed as 2⋅i+1$2\cdot i+1$.

           1
          / \
         /   \
        /     \
       /       \
      2         3
     / \       / \
    /   \     /   \
   4     5   6     7

   and so on...

Veronica tells this new numbering scheme to her dad, Keith, and and then inserts n$n$ distinct numbers, a0,a1,…,an−1$a_0,a_1,\dots ,a_{n-1}$, into a BST in increasing order of indices. Because he's better at hitting bad guys than hitting books, Keith promptly forgets the numbering scheme and asks for your help!

For each number ai$a_i$, print the index of the node where it's located in the BST. See the Explanationsection for more detail.

Input Format

The first line contains a single integer, n$n$, denoting the number of nodes in the tree. 
The second line contains n$n$ space-separated integers describing the respective integer elements, a0$a_0$through an−1$a_{n-1}$.

Constraints

• 1≤ai≤109$1\le a_i\le {10}^9$
• 1≤n≤103$1\le n\le {10}^3$ for 30%$30\mathrm{\%}$ of the test cases.
• 1≤n≤3×105$1\le n\le 3\times {10}^5$ for 100%$100\mathrm{\%}$ of the test cases.

Output Format

Print a single line of n$n$ space-separated integers where the ith$i^{th}$ number denotes the node index where number ai$a_i$ is present in the BST. As these numbers may be large, output them modulo 109+7${10}^9+7$.

Sample Input 0

4
5 3 6 2

Sample Output 0

1 2 3 4

Sample Input 1

3
1 2 3

Sample Output 1

1 3 7

Explanation

Sample Case 0:

The BST formed is:

     5(1)
    / \
   /   \
  3(2)  6(3)
 /
2(4)

* The node indices are written in parentheses.

Sample Case 1: 
The BST formed is

1(1)
 \
  \
   2(3)
    \
     \
      3(7)

* The node indices are written in parentheses.

-------------------------------------EDITORIAL---------------------------------------------------------------------

• roblem
• Submissions
• Leaderboard
• Discussions
• Editorial

 Editorial by darkshadows

Approach 1(Brute Force):

In this approach you keep building the Binary Search Tree in a simple way. That is, you insert a new value in O(h)$O(h)$where h=$h=$ current height of BST.
Worst case complexity of such an approach is O(n2)$O(n^2)$, because worst case height of BST can be O(n)$O(n)$.

Approach 2(Intelligent):

For each position where a new number can be inserted, we can define a range of valid numbers that can be inserted at that poisition. For example, in this BST:

  5
 / \
2   8
     \
      19
     /
    10 

For left child of 2, the range is (−inf,2)$(-inf,2)$ where (a,b)$(a,b)$ denotes all valid integers in range a$a$ to b$b$(excluding both a$a$and b$b$). Similarly, for right child the range is (2,5)$(2,5)$.
For left child of 8, the range is (5,8)$(5,8)$. For right left child of 10, the range is (8,10)$(8,10)$ and for right child the range is (10,19)$(10,19)$. For right child of 19 the range is (19,inf)$(19,inf)$.

So, all the ranges are (−inf,2)$(-inf,2)$, (2,5)$(2,5)$, (5,8)$(5,8)$, (8,10)$(8,10)$, (10,19)$(10,19)$, (19,inf)$(19,inf)$. Another interesting observation is that all these ranges are disjoint and the break points of these ranges are the values that already exist in the BST.

Now, with these ranges we can also associate the new index a number will have if it's inserted into the tree. So, in this case, the mappings from ranges to indexes will be:

inf, 2  :   4
2, 5    :   5
5, 8    :   6
8, 10   :   28
10, 19  :   29
19, inf :   15

Now, let's say you want to insert x=9$x=9$, in the BST. You know that it occurs in the range (8,10)$(8,10)$ so, index of x$x$ will be 29. Now, this range has been destroyed and two new ranges (8,9)$(8,9)$ and (9,10)$(9,10)$ have been created with indexes2∗28$2\ast 28$ and 2∗28+1$2\ast 28+1$, respectively.

Implementation:
How do we actually implement this? We maintain a map from ranges to indexes as shown in example above. Let's say we get a value x$x$, how do we find the range in which it lies. Since break points of ranges are the values already existing in the BST and all ranges are disjoint, the range of x$x$ is (x1,x2)$(x1,x2)$, where x1$x1$ is the largest number smaller than x$x$ in the BST and x2$x2$ is the smallest number larger than x$x$ in the BST. These two values can be easily found via a set in C++. Now, we search for the range in the map, print the answer for x$x$ and remove the existing range and update two new ranges in the map.

Overall complexity is O(NlogN)$O(NlogN)$.

 Set by darkshadows

Problem Setter's code :

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007ll
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
    //map of ranges
    map <pair<int,int> , LL > mymap;
    map <pair<int,int> , LL >::iterator itt;

    //set of values inserted into BST
    set<int> myset;
    set<int> myn;
    set<int>::iterator it;

    int n;

    //define range for root
    mymap[mp(INT_MIN,INT_MAX)]=1;

    //scan n
    sd(n);
    assert(n>=1&&n<=300000);
    for(int i=0; i<n; i++){
        int x,l,r;
        //scan A_i
        sd(x);
        assert(x>=1&&x<=1000000000);
        //find the range in which it lies ie. (x1, x2)
        myset.insert(x);
        it=myset.find(x);
        if(it==myset.begin())l=INT_MIN;
        else{
            it--;
            l=*it;
            it++;
        }
        it++;
        if(it==myset.end())r=INT_MAX;
        else r=*it;

        //search for the range in map
        itt=mymap.find(mp(l,r));
        assert(itt!=mymap.end());

        //insert two new ranges into the map
        mymap[mp(l,x)]=(2ll*itt->S)%MOD;
        mymap[mp(x,r)]=(2ll*itt->S+1ll)%MOD;

        //output answer
        cout << itt->S;
        if(i!=n-1)cout << " ";
        else cout << endl;

        //erase existing range from the map
        mymap.erase(itt);
    }
    return 0;
}