You are given a set Y of n distinct positive integersy₁,?y₂,?...,?y_n.

Set X of ndistinct positive integers x₁,?x₂,?...,?x_n is said togenerate set Y if one can transformX to Y by applying some number of the following two Operation to integers inX:

Note that integers in X are not required to be distinct after each operation.

Two sets of distinct integers X and Y are equal if they are equal as sets. In other Words, if we write elements of the sets in the array in the increasing order, these arrays would be equal.

Note, that any set of integers (or its permutation) generates itself.

You are given a set Y and have to find a setX that generates Y and themaximum element of X is mininum possible.

The first line of the input contains a single integer n (1?≤?n?≤?50?000) — the number of elements inY.

The second line contains n integers y₁,?...,?y_n (1?≤?y_i?≤?10⁹), that are guaranteed to be distinct.

PRint n integers — set of distinct integers that generateY and the maximum element of which is minimum possible. If there are several such sets, print any of them.

51 2 3 4 5Output
4 5 2 3 1 Input
615 14 3 13 1 12Output
12 13 14 7 3 1 Input
69 7 13 17 5 11Output
4 5 2 6 3 1 
題目大意：
讓你構造一個長度為N的數組X【】，使得其能夠通過兩種操作得到數組Y【】；
現在給你一個數組Y【】，讓你構造一個可行X【】，使得其中最大值盡可能的小。
兩種操作：
選擇x【i】，使得其變成X【i】*2或者是X【i】*2+1.....
保證Y【】是一個不包含重復元素的數組，要求X【】也不能包含重復元素。而且所有元素大于0.
思路：
1、考慮問題本質，其實我們最開始可以設定ans【】（X【】）就是Y【】；
然后盡可能的縮小最大值，來尋找一個最終序列，使得X【】中最大元素盡可能的小。
2、那么首先我們將數組Y【】從大到小排序，然后全部塞到一個優先隊列中，每次我們拿出最大值，肯定想要做到的就是將這個數變小，變成一個和此時隊列中所有元素不相同的小值。
那么我們每一次取隊頭元素，將其盡可能的變小，如果可以變小，再將變小的值塞進隊列，繼續取隊頭，循環往復。
直到不能變小為止，停止操作即可。
Ac代碼：
#include<stdio.h>#include<algorithm>#include<string.h>#include<map>#include<queue>using namespace std;struct node{    int val;    friend bool operator <(node a,node b)    {        return a.val<b.val;    }}nod;int a[50050];int ans[50050];int b[500];int main(){    int n;    while(~scanf("%d",&n))    {        for(int i=0;i<n;i++)scanf("%d",&a[i]);        sort(a,a+n);reverse(a,a+n);        priority_queue<node>s;        map<int ,int >ss;        for(int i=0;i<n;i++)        {            nod.val=a[i];            ss[a[i]]=1;            s.push(nod);        }        while(1)        {            int flag=0;            nod=s.top();            while(nod.val)            {                nod.val/=2;                if(ss[nod.val]==0&&nod.val!=0)                {                    flag=1;                    ss[nod.val]=1;                    s.pop();                    s.push(nod);                    break;                }            }            if(flag==0)break;        }        while(!s.empty())        {            nod=s.top();            s.pop();            printf("%d ",nod.val);        }        printf("/n");    }}