描述

HIHO银行等待区有一排N个座位，从左到右依次编号1~N。现在有M位顾客坐在座位上，其中第i位坐在编号Ai的座位上。

之后又陆续来了K位顾客，(K + M ≤ N) 他们都会选择坐在最"舒适"的空座位上，并且过程中没有顾客离开自己的座位。

最"舒适"的定义是：

1. 对于一个座位，我们将它左边连续的空座位数目记作X，它右边连续的空座位数目记作Y。

2. 顾客首先会选择min(X, Y)最大的座位。

3. 如果有多个选择，顾客会选择其中max(X, Y)最大的座位。

4. 如果还是有多个选择，顾客会选择其中编号最小的座位。

请你计算出之后来的K位顾客坐在几号座位上。

输入

第一行包含三个整数N，M和K。

第二行包含M个整数A1, A2, ... AM。

对于50%的数据，1 ≤ N ≤ 1000

对于100%的数据，1 ≤ N ≤ 100000,  1 ≤ Ai ≤ N,  K + M ≤ N

输出

输出K行，每行一个整数代表该位顾客座位的编号。

#include<queue>

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

struct in

{

    int id;int l;int r;

    in(){}

    in(int x,int y,int z):id(x),l(y),r(z){}

    friend bool operator < (in a,in b){

        if(a.r-a.l==b.r-b.l) return a.id>b.id;

        return a.r-a.l<b.r-b.l;

    }

};

int a[maxn],used[maxn],L[maxn],R[maxn];

priority_queue<in>q;

int main()

{

    int N,M,K,i,j;

    scanf("%d%d%d",&N,&M,&K);

    used[]=; used[N+]=;

    for(i=;i<=M;i++) scanf("%d",&a[i]);

    sort(a+,a+M+);

    a[]=;a[M+]=N+;

    for(i=;i<=M+;i++) {

        L[i]=a[i-]+; R[i]=a[i]-;

        q.push(in((L[i]+R[i])/,L[i],R[i]));

    }

    for(i=;i<=K;i++){

        in tmp=q.top(); q.pop();

        printf("%d\n",tmp.id);

        q.push(in((tmp.id-+tmp.l)/,tmp.l,tmp.id-));

        q.push(in((tmp.r+tmp.id+)/,tmp.id+,tmp.r));

    }

    return ;

}