#import <stdio.h>
#import <stdlib.h>
typedef long long INT;

typedef struct Pair {
    INT index;
    INT value;
} Pair;

int compare_value(const void *a, const void *b) {
    INT diff = ((Pair*)a)->value - ((Pair*)b)->value;
    return diff>0 ? 1: diff<0 ? -1 : 0;
}

int compare_index(const void *a, const void *b) {
    INT diff = ((Pair*)a)->index - ((Pair*)b)->index;
    return diff>0 ? 1: diff<0 ? -1 : 0;
}

int main(){
    INT N;
    scanf("%lld",&N);
    Pair X[200002];
    for(INT i=0;i<N;i++){
        INT x;
        scanf("%lld",&x);
        Pair p = {i, x};
        X[i] = p;
    }
    qsort(X, N, sizeof(Pair), compare_value);
    INT mid1 = X[N/2].value;
    INT mid2 = X[N/2-1].value;
    for(INT i=0;i<N;i++){
        X[i].value = (i<N/2) ? mid1 : mid2;
    }
    qsort(X, N, sizeof(Pair), compare_index);
    for(INT i=0;i<N;i++){
        printf("%lld\n", X[i].value);
    }
}

; ModuleID = '/data/TheStack_IR/OJ_Samples/Collated/ObjectiveC/Source_559/source.m'
source_filename = "/data/TheStack_IR/OJ_Samples/Collated/ObjectiveC/Source_559/source.m"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

%struct.Pair = type { i64, i64 }

@.str = private unnamed_addr constant [5 x i8] c"%lld\00", align 1
@.str.1 = private unnamed_addr constant [6 x i8] c"%lld\0A\00", align 1

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: read) uwtable
define dso_local i32 @compare_value(ptr nocapture noundef readonly %a, ptr nocapture noundef readonly %b) #0 {
entry:
  %value = getelementptr inbounds %struct.Pair, ptr %a, i64 0, i32 1
  %0 = load i64, ptr %value, align 8, !tbaa !5
  %value1 = getelementptr inbounds %struct.Pair, ptr %b, i64 0, i32 1
  %1 = load i64, ptr %value1, align 8, !tbaa !5
  %cmp = icmp sgt i64 %0, %1
  %cmp2.not = icmp ne i64 %0, %1
  %cond = sext i1 %cmp2.not to i32
  %cond3 = select i1 %cmp, i32 1, i32 %cond
  ret i32 %cond3
}

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: read) uwtable
define dso_local i32 @compare_index(ptr nocapture noundef readonly %a, ptr nocapture noundef readonly %b) #0 {
entry:
  %0 = load i64, ptr %a, align 8, !tbaa !10
  %1 = load i64, ptr %b, align 8, !tbaa !10
  %cmp = icmp sgt i64 %0, %1
  %cmp2.not = icmp ne i64 %0, %1
  %cond = sext i1 %cmp2.not to i32
  %cond3 = select i1 %cmp, i32 1, i32 %cond
  ret i32 %cond3
}

; Function Attrs: nofree nounwind uwtable
define dso_local i32 @main() local_unnamed_addr #2 {
entry:
  %N = alloca i64, align 8
  %X = alloca [200002 x %struct.Pair], align 16
  %x = alloca i64, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %N) #5
  %call = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull %N)
  call void @llvm.lifetime.start.p0(i64 3200032, ptr nonnull %X) #5
  %0 = load i64, ptr %N, align 8, !tbaa !11
  %cmp40 = icmp sgt i64 %0, 0
  br i1 %cmp40, label %for.body, label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.body, %entry
  %.lcssa = phi i64 [ %0, %entry ], [ %6, %for.body ]
  call void @qsort(ptr noundef nonnull %X, i64 noundef %.lcssa, i64 noundef 16, ptr noundef nonnull @compare_value) #5
  %1 = load i64, ptr %N, align 8, !tbaa !11
  %div = sdiv i64 %1, 2
  %value3 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %div, i32 1
  %2 = load i64, ptr %value3, align 8, !tbaa !5
  %sub = add nsw i64 %div, -1
  %value6 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %sub, i32 1
  %3 = load i64, ptr %value6, align 8, !tbaa !5
  %cmp942 = icmp sgt i64 %1, 0
  br i1 %cmp942, label %for.body11.preheader, label %for.cond.cleanup10

for.body11.preheader:                             ; preds = %for.cond.cleanup
  %xtraiter = and i64 %1, 3
  %4 = icmp ult i64 %1, 4
  br i1 %4, label %for.cond.cleanup10.loopexit.unr-lcssa, label %for.body11.preheader.new

for.body11.preheader.new:                         ; preds = %for.body11.preheader
  %unroll_iter = and i64 %1, -4
  br label %for.body11

for.body:                                         ; preds = %entry, %for.body
  %i.041 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %x) #5
  %call1 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull %x)
  %5 = load i64, ptr %x, align 8, !tbaa !11
  %arrayidx = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %i.041
  store i64 %i.041, ptr %arrayidx, align 16, !tbaa.struct !12
  %p.sroa.4.0.arrayidx.sroa_idx = getelementptr inbounds i8, ptr %arrayidx, i64 8
  store i64 %5, ptr %p.sroa.4.0.arrayidx.sroa_idx, align 8, !tbaa.struct !13
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %x) #5
  %inc = add nuw nsw i64 %i.041, 1
  %6 = load i64, ptr %N, align 8, !tbaa !11
  %cmp = icmp slt i64 %inc, %6
  br i1 %cmp, label %for.body, label %for.cond.cleanup

for.cond.cleanup10.loopexit.unr-lcssa:            ; preds = %for.body11, %for.body11.preheader
  %i7.043.unr = phi i64 [ 0, %for.body11.preheader ], [ %inc17.3, %for.body11 ]
  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
  br i1 %lcmp.mod.not, label %for.cond.cleanup10, label %for.body11.epil

for.body11.epil:                                  ; preds = %for.cond.cleanup10.loopexit.unr-lcssa, %for.body11.epil
  %i7.043.epil = phi i64 [ %inc17.epil, %for.body11.epil ], [ %i7.043.unr, %for.cond.cleanup10.loopexit.unr-lcssa ]
  %epil.iter = phi i64 [ %epil.iter.next, %for.body11.epil ], [ 0, %for.cond.cleanup10.loopexit.unr-lcssa ]
  %cmp13.epil = icmp slt i64 %i7.043.epil, %div
  %cond.epil = select i1 %cmp13.epil, i64 %2, i64 %3
  %value15.epil = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %i7.043.epil, i32 1
  store i64 %cond.epil, ptr %value15.epil, align 8, !tbaa !5
  %inc17.epil = add nuw nsw i64 %i7.043.epil, 1
  %epil.iter.next = add i64 %epil.iter, 1
  %epil.iter.cmp.not = icmp eq i64 %epil.iter.next, %xtraiter
  br i1 %epil.iter.cmp.not, label %for.cond.cleanup10, label %for.body11.epil, !llvm.loop !14

for.cond.cleanup10:                               ; preds = %for.cond.cleanup10.loopexit.unr-lcssa, %for.body11.epil, %for.cond.cleanup
  call void @qsort(ptr noundef nonnull %X, i64 noundef %1, i64 noundef 16, ptr noundef nonnull @compare_index) #5
  %7 = load i64, ptr %N, align 8, !tbaa !11
  %cmp2244 = icmp sgt i64 %7, 0
  br i1 %cmp2244, label %for.body24, label %for.cond.cleanup23

for.body11:                                       ; preds = %for.body11, %for.body11.preheader.new
  %i7.043 = phi i64 [ 0, %for.body11.preheader.new ], [ %inc17.3, %for.body11 ]
  %niter = phi i64 [ 0, %for.body11.preheader.new ], [ %niter.next.3, %for.body11 ]
  %cmp13 = icmp slt i64 %i7.043, %div
  %cond = select i1 %cmp13, i64 %2, i64 %3
  %value15 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %i7.043, i32 1
  store i64 %cond, ptr %value15, align 8, !tbaa !5
  %inc17 = or i64 %i7.043, 1
  %cmp13.1 = icmp slt i64 %inc17, %div
  %cond.1 = select i1 %cmp13.1, i64 %2, i64 %3
  %value15.1 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %inc17, i32 1
  store i64 %cond.1, ptr %value15.1, align 8, !tbaa !5
  %inc17.1 = or i64 %i7.043, 2
  %cmp13.2 = icmp slt i64 %inc17.1, %div
  %cond.2 = select i1 %cmp13.2, i64 %2, i64 %3
  %value15.2 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %inc17.1, i32 1
  store i64 %cond.2, ptr %value15.2, align 8, !tbaa !5
  %inc17.2 = or i64 %i7.043, 3
  %cmp13.3 = icmp slt i64 %inc17.2, %div
  %cond.3 = select i1 %cmp13.3, i64 %2, i64 %3
  %value15.3 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %inc17.2, i32 1
  store i64 %cond.3, ptr %value15.3, align 8, !tbaa !5
  %inc17.3 = add nuw nsw i64 %i7.043, 4
  %niter.next.3 = add i64 %niter, 4
  %niter.ncmp.3 = icmp eq i64 %niter.next.3, %unroll_iter
  br i1 %niter.ncmp.3, label %for.cond.cleanup10.loopexit.unr-lcssa, label %for.body11

for.cond.cleanup23:                               ; preds = %for.body24, %for.cond.cleanup10
  call void @llvm.lifetime.end.p0(i64 3200032, ptr nonnull %X) #5
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %N) #5
  ret i32 0

for.body24:                                       ; preds = %for.cond.cleanup10, %for.body24
  %i20.045 = phi i64 [ %inc29, %for.body24 ], [ 0, %for.cond.cleanup10 ]
  %value26 = getelementptr inbounds [200002 x %struct.Pair], ptr %X, i64 0, i64 %i20.045, i32 1
  %8 = load i64, ptr %value26, align 8, !tbaa !5
  %call27 = call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.1, i64 noundef %8)
  %inc29 = add nuw nsw i64 %i20.045, 1
  %9 = load i64, ptr %N, align 8, !tbaa !11
  %cmp22 = icmp slt i64 %inc29, %9
  br i1 %cmp22, label %for.body24, label %for.cond.cleanup23
}

; Function Attrs: nofree nounwind
declare noundef i32 @__isoc99_scanf(ptr nocapture noundef readonly, ...) local_unnamed_addr #3

; Function Attrs: nofree
declare void @qsort(ptr noundef, i64 noundef, i64 noundef, ptr nocapture noundef) local_unnamed_addr #4

; Function Attrs: nofree nounwind
declare noundef i32 @printf(ptr nocapture noundef readonly, ...) local_unnamed_addr #3

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: read) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { nofree nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nofree nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #4 = { nofree "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { nounwind }

!llvm.linker.options = !{}
!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"Ubuntu clang version 18.0.0 (++20231007042255+8abb2ace888b-1~exp1~20231007042414.1230)"}
!5 = !{!6, !7, i64 8}
!6 = !{!"Pair", !7, i64 0, !7, i64 8}
!7 = !{!"long long", !8, i64 0}
!8 = !{!"omnipotent char", !9, i64 0}
!9 = !{!"Simple C/C++ TBAA"}
!10 = !{!6, !7, i64 0}
!11 = !{!7, !7, i64 0}
!12 = !{i64 0, i64 8, !11, i64 8, i64 8, !11}
!13 = !{i64 0, i64 8, !11}
!14 = distinct !{!14, !15}
!15 = !{!"llvm.loop.unroll.disable"}
