program Divide_the_problems
    implicit none
    integer(4):: n
    integer(4),allocatable:: d(:)

    read*, n
    allocate(d(n))
    read*, d(:)

    call merge_sort(d,1,n)
    print*, d(n/2+1)-d(n/2)
contains
    recursive subroutine merge_sort(ar, fst, lst)
        integer(4),intent(inout):: ar(:)
        integer(4),intent(in):: fst,lst
        integer(4):: mdl

        if (lst - fst < 2) then
            if (ar(fst) > ar(lst)) call swap(ar(fst),ar(lst))
            return
        end if

        mdl = (fst+lst)/2
        call merge_sort(ar,fst,mdl)
        call merge_sort(ar,mdl+1,lst)
        call merge_(ar,fst,mdl,lst)
    end subroutine

    subroutine merge_(ar,fst,mdl,lst)
        integer(4),intent(inout):: ar(:)
        integer(4),intent(in):: fst,mdl,lst
        integer(4),allocatable:: tmp(:)
        integer(4):: li,ri,ti

        allocate(tmp(lst-fst+1))

        li=fst
        ri=mdl+1
        ti=1

        do while(li <= mdl .and. ri <= lst)
            if (ar(li) <= ar(ri)) then
                tmp(ti) = ar(li)
                li=li+1
            else
                tmp(ti) = ar(ri)
                ri=ri+1
            end if
            ti=ti+1
        end do

        if (li <= mdl) then
            tmp(ti:) = ar(li:mdl)
        else
            tmp(ti:) = ar(ri:lst)
        end if

        ar(fst:lst) = tmp(:)
        deallocate(tmp)
    end subroutine


    subroutine swap(x,y)
        integer(4),intent(inout):: x,y
        integer(4):: t
        t=x
        x=y
        y=t
    end subroutine
end program Divide_the_problems
; ModuleID = 'FIRModule'
source_filename = "FIRModule"
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"

@_QFEd.0 = internal unnamed_addr global ptr null
@_QFEd.8 = internal unnamed_addr global i64 0
@_QQcl.e3ca4d2cad4fab5d4d77daf09769c130 = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_3886/source.f\00"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #0

; Function Attrs: mustprogress nounwind willreturn allockind("free") memory(argmem: readwrite, inaccessiblemem: readwrite)
declare void @free(ptr allocptr nocapture noundef) local_unnamed_addr #1

define void @_QQmain() local_unnamed_addr {
  %1 = alloca { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, align 8
  %2 = alloca { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, align 8
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = tail call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.e3ca4d2cad4fab5d4d77daf09769c130, i32 6)
  %6 = call i1 @_FortranAioInputInteger(ptr %5, ptr nonnull %4, i32 4)
  %7 = call i32 @_FortranAioEndIoStatement(ptr %5)
  %8 = load i32, ptr %4, align 4, !tbaa !3
  %9 = call i32 @llvm.smax.i32(i32 %8, i32 0)
  %10 = zext i32 %9 to i64
  %11 = shl nuw nsw i64 %10, 2
  %12 = call ptr @malloc(i64 %11)
  store ptr %12, ptr @_QFEd.0, align 8, !tbaa !7
  store i64 %10, ptr @_QFEd.8, align 8, !tbaa !7
  %13 = call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.e3ca4d2cad4fab5d4d77daf09769c130, i32 8)
  %.unpack = load ptr, ptr @_QFEd.0, align 8, !tbaa !7
  %.unpack133.unpack.unpack135 = load i64, ptr @_QFEd.8, align 8, !tbaa !7
  %14 = call i64 @llvm.smax.i64(i64 %.unpack133.unpack.unpack135, i64 0)
  store ptr %.unpack, ptr %2, align 8, !tbaa !7
  %.fca.1.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 1
  store i64 4, ptr %.fca.1.gep, align 8, !tbaa !7
  %.fca.2.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 2
  store i32 20180515, ptr %.fca.2.gep, align 8, !tbaa !7
  %.fca.3.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 3
  store i8 1, ptr %.fca.3.gep, align 4, !tbaa !7
  %.fca.4.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 4
  store i8 9, ptr %.fca.4.gep, align 1, !tbaa !7
  %.fca.5.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 5
  store i8 0, ptr %.fca.5.gep, align 2, !tbaa !7
  %.fca.6.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 6
  store i8 0, ptr %.fca.6.gep, align 1, !tbaa !7
  %.fca.7.0.0.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 7, i64 0, i64 0
  store i64 1, ptr %.fca.7.0.0.gep, align 8, !tbaa !7
  %.fca.7.0.1.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 7, i64 0, i64 1
  store i64 %14, ptr %.fca.7.0.1.gep, align 8, !tbaa !7
  %.fca.7.0.2.gep = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %2, i64 0, i32 7, i64 0, i64 2
  store i64 4, ptr %.fca.7.0.2.gep, align 8, !tbaa !7
  %15 = call i1 @_FortranAioInputDescriptor(ptr %13, ptr nonnull %2)
  %16 = call i32 @_FortranAioEndIoStatement(ptr %13)
  %.unpack138 = load ptr, ptr @_QFEd.0, align 8, !tbaa !7
  %.unpack145.unpack.unpack147 = load i64, ptr @_QFEd.8, align 8, !tbaa !7
  store ptr %.unpack138, ptr %1, align 8, !tbaa !7
  %.fca.1.gep71 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 1
  store i64 4, ptr %.fca.1.gep71, align 8, !tbaa !7
  %.fca.2.gep73 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 2
  store i32 20180515, ptr %.fca.2.gep73, align 8, !tbaa !7
  %.fca.3.gep75 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 3
  store i8 1, ptr %.fca.3.gep75, align 4, !tbaa !7
  %.fca.4.gep77 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 4
  store i8 9, ptr %.fca.4.gep77, align 1, !tbaa !7
  %.fca.5.gep79 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 5
  store i8 0, ptr %.fca.5.gep79, align 2, !tbaa !7
  %.fca.6.gep81 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 6
  store i8 0, ptr %.fca.6.gep81, align 1, !tbaa !7
  %.fca.7.0.0.gep83 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 7, i64 0, i64 0
  store i64 1, ptr %.fca.7.0.0.gep83, align 8, !tbaa !7
  %.fca.7.0.1.gep85 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 7, i64 0, i64 1
  store i64 %.unpack145.unpack.unpack147, ptr %.fca.7.0.1.gep85, align 8, !tbaa !7
  %.fca.7.0.2.gep87 = getelementptr inbounds { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %1, i64 0, i32 7, i64 0, i64 2
  store i64 4, ptr %.fca.7.0.2.gep87, align 8, !tbaa !7
  store i32 1, ptr %3, align 4, !tbaa !3
  call void @_QFPmerge_sort(ptr nonnull %1, ptr nonnull %3, ptr nonnull %4)
  %17 = call ptr @_FortranAioBeginExternalListOutput(i32 -1, ptr nonnull @_QQcl.e3ca4d2cad4fab5d4d77daf09769c130, i32 11)
  %.unpack150 = load ptr, ptr @_QFEd.0, align 8, !tbaa !7
  %18 = load i32, ptr %4, align 4, !tbaa !3
  %19 = sdiv i32 %18, 2
  %20 = sext i32 %19 to i64
  %21 = getelementptr i32, ptr %.unpack150, i64 %20
  %22 = load i32, ptr %21, align 4, !tbaa !3
  %narrow = add nsw i32 %19, -1
  %23 = sext i32 %narrow to i64
  %24 = getelementptr i32, ptr %.unpack150, i64 %23
  %25 = load i32, ptr %24, align 4, !tbaa !3
  %26 = sub i32 %22, %25
  %27 = call i1 @_FortranAioOutputInteger32(ptr %17, i32 %26)
  %28 = call i32 @_FortranAioEndIoStatement(ptr %17)
  ret void
}

; Function Attrs: nounwind
define void @_QFPmerge_sort(ptr %0, ptr nocapture readonly %1, ptr nocapture readonly %2) local_unnamed_addr #2 {
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = load i32, ptr %2, align 4, !tbaa !3
  %7 = load i32, ptr %1, align 4, !tbaa !3
  %8 = sub i32 %6, %7
  %9 = icmp slt i32 %8, 2
  br i1 %9, label %10, label %26

10:                                               ; preds = %3
  %11 = sext i32 %7 to i64
  %12 = add nsw i64 %11, -1
  %13 = load ptr, ptr %0, align 8, !tbaa !7
  %14 = getelementptr { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %0, i64 0, i32 7, i64 0, i64 2
  %15 = load i64, ptr %14, align 8, !tbaa !7
  %16 = mul i64 %15, %12
  %17 = getelementptr i8, ptr %13, i64 %16
  %18 = load i32, ptr %17, align 4, !tbaa !3
  %19 = sext i32 %6 to i64
  %20 = add nsw i64 %19, -1
  %21 = mul i64 %15, %20
  %22 = getelementptr i8, ptr %13, i64 %21
  %23 = load i32, ptr %22, align 4, !tbaa !3
  %24 = icmp sgt i32 %18, %23
  br i1 %24, label %25, label %30

25:                                               ; preds = %10
  store i32 %23, ptr %17, align 4, !tbaa !3
  store i32 %18, ptr %22, align 4, !tbaa !3
  br label %30

26:                                               ; preds = %3
  %27 = add i32 %7, %6
  %28 = sdiv i32 %27, 2
  store i32 %28, ptr %5, align 4, !tbaa !3
  call void @_QFPmerge_sort(ptr %0, ptr nonnull %1, ptr nonnull %5)
  %29 = add nsw i32 %28, 1
  store i32 %29, ptr %4, align 4, !tbaa !3
  call void @_QFPmerge_sort(ptr %0, ptr nonnull %4, ptr nonnull %2)
  call void @_QFPmerge_(ptr %0, ptr nonnull %1, ptr nonnull %5, ptr nonnull %2)
  br label %30

30:                                               ; preds = %25, %10, %26
  ret void
}

; Function Attrs: nounwind
define void @_QFPmerge_(ptr nocapture readonly %0, ptr nocapture readonly %1, ptr nocapture readonly %2, ptr nocapture readonly %3) local_unnamed_addr #2 {
  %5 = load i32, ptr %3, align 4, !tbaa !3
  %6 = load i32, ptr %1, align 4, !tbaa !3
  %7 = add i32 %5, 1
  %8 = sub i32 %7, %6
  %9 = tail call i32 @llvm.smax.i32(i32 %8, i32 0)
  %10 = zext i32 %9 to i64
  %11 = shl nuw nsw i64 %10, 2
  %12 = tail call ptr @malloc(i64 %11)
  %13 = load i32, ptr %2, align 4, !tbaa !3
  %14 = add i32 %13, 1
  %15 = icmp sle i32 %6, %13
  %16 = icmp sle i32 %14, %5
  %17 = and i1 %16, %15
  br i1 %17, label %.lr.ph, label %._crit_edge

.lr.ph:                                           ; preds = %4
  %18 = load ptr, ptr %0, align 8, !tbaa !7
  %19 = getelementptr { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %0, i64 0, i32 7, i64 0, i64 2
  %20 = load i64, ptr %19, align 8, !tbaa !7
  br label %21

21:                                               ; preds = %.lr.ph, %39
  %.040 = phi i32 [ %6, %.lr.ph ], [ %.1, %39 ]
  %.02939 = phi i32 [ %14, %.lr.ph ], [ %.130, %39 ]
  %.03138 = phi i32 [ 1, %.lr.ph ], [ %40, %39 ]
  %22 = sext i32 %.040 to i64
  %23 = add nsw i64 %22, -1
  %24 = mul i64 %20, %23
  %25 = getelementptr i8, ptr %18, i64 %24
  %26 = load i32, ptr %25, align 4, !tbaa !3
  %27 = sext i32 %.02939 to i64
  %28 = add nsw i64 %27, -1
  %29 = mul i64 %20, %28
  %30 = getelementptr i8, ptr %18, i64 %29
  %31 = load i32, ptr %30, align 4, !tbaa !3
  %.not = icmp sgt i32 %26, %31
  %32 = sext i32 %.03138 to i64
  %33 = add nsw i64 %32, -1
  %34 = getelementptr i32, ptr %12, i64 %33
  br i1 %.not, label %37, label %35

35:                                               ; preds = %21
  store i32 %26, ptr %34, align 4, !tbaa !3
  %36 = add i32 %.040, 1
  br label %39

37:                                               ; preds = %21
  store i32 %31, ptr %34, align 4, !tbaa !3
  %38 = add i32 %.02939, 1
  br label %39

39:                                               ; preds = %35, %37
  %.130 = phi i32 [ %.02939, %35 ], [ %38, %37 ]
  %.1 = phi i32 [ %36, %35 ], [ %.040, %37 ]
  %40 = add i32 %.03138, 1
  %41 = icmp sle i32 %.1, %13
  %42 = icmp sle i32 %.130, %5
  %43 = and i1 %42, %41
  br i1 %43, label %21, label %._crit_edge.loopexit

._crit_edge.loopexit:                             ; preds = %39
  %44 = sext i32 %40 to i64
  br i1 %41, label %45, label %66

._crit_edge:                                      ; preds = %4
  br i1 %15, label %45, label %66

45:                                               ; preds = %._crit_edge.loopexit, %._crit_edge
  %.0.lcssa57 = phi i32 [ %.1, %._crit_edge.loopexit ], [ %6, %._crit_edge ]
  %.031.lcssa54 = phi i64 [ %44, %._crit_edge.loopexit ], [ 1, %._crit_edge ]
  %46 = sub nsw i64 %10, %.031.lcssa54
  %47 = sext i32 %.0.lcssa57 to i64
  %48 = icmp sgt i64 %46, -1
  br i1 %48, label %.lr.ph47, label %.loopexit

.lr.ph47:                                         ; preds = %45
  %49 = add nuw nsw i64 %46, 1
  %50 = getelementptr { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %0, i64 0, i32 7, i64 0, i64 2
  %51 = load i64, ptr %50, align 8, !tbaa !7
  %52 = load ptr, ptr %0, align 8, !tbaa !7
  br label %53

53:                                               ; preds = %.lr.ph47, %53
  %54 = phi i64 [ %49, %.lr.ph47 ], [ %64, %53 ]
  %55 = phi i64 [ 0, %.lr.ph47 ], [ %56, %53 ]
  %56 = add nuw nsw i64 %55, 1
  %57 = add nsw i64 %55, -1
  %58 = add nsw i64 %57, %47
  %59 = mul i64 %51, %58
  %60 = getelementptr i8, ptr %52, i64 %59
  %61 = load i32, ptr %60, align 4, !tbaa !3
  %62 = add nsw i64 %57, %.031.lcssa54
  %63 = getelementptr i32, ptr %12, i64 %62
  store i32 %61, ptr %63, align 4, !tbaa !3
  %64 = add nsw i64 %54, -1
  %65 = icmp ugt i64 %54, 1
  br i1 %65, label %53, label %.loopexit

66:                                               ; preds = %._crit_edge.loopexit, %._crit_edge
  %.029.lcssa56 = phi i32 [ %.130, %._crit_edge.loopexit ], [ %14, %._crit_edge ]
  %.031.lcssa55 = phi i64 [ %44, %._crit_edge.loopexit ], [ 1, %._crit_edge ]
  %67 = sub nsw i64 %10, %.031.lcssa55
  %68 = sext i32 %.029.lcssa56 to i64
  %69 = icmp sgt i64 %67, -1
  br i1 %69, label %.lr.ph45, label %.loopexit

.lr.ph45:                                         ; preds = %66
  %70 = add nuw nsw i64 %67, 1
  %71 = getelementptr { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %0, i64 0, i32 7, i64 0, i64 2
  %72 = load i64, ptr %71, align 8, !tbaa !7
  %73 = load ptr, ptr %0, align 8, !tbaa !7
  br label %74

74:                                               ; preds = %.lr.ph45, %74
  %75 = phi i64 [ %70, %.lr.ph45 ], [ %85, %74 ]
  %76 = phi i64 [ 0, %.lr.ph45 ], [ %77, %74 ]
  %77 = add nuw nsw i64 %76, 1
  %78 = add nsw i64 %76, -1
  %79 = add nsw i64 %78, %68
  %80 = mul i64 %72, %79
  %81 = getelementptr i8, ptr %73, i64 %80
  %82 = load i32, ptr %81, align 4, !tbaa !3
  %83 = add nsw i64 %78, %.031.lcssa55
  %84 = getelementptr i32, ptr %12, i64 %83
  store i32 %82, ptr %84, align 4, !tbaa !3
  %85 = add nsw i64 %75, -1
  %86 = icmp ugt i64 %75, 1
  br i1 %86, label %74, label %.loopexit

.loopexit:                                        ; preds = %74, %53, %66, %45
  %87 = sext i32 %6 to i64
  %88 = sext i32 %5 to i64
  %89 = sub nsw i64 %88, %87
  %90 = icmp sgt i64 %89, -1
  br i1 %90, label %.lr.ph49, label %._crit_edge50

.lr.ph49:                                         ; preds = %.loopexit
  %91 = add nuw nsw i64 %89, 1
  %92 = add nsw i64 %87, -1
  %93 = getelementptr { ptr, i64, i32, i8, i8, i8, i8, [1 x [3 x i64]] }, ptr %0, i64 0, i32 7, i64 0, i64 2
  %94 = load i64, ptr %93, align 8, !tbaa !7
  %95 = load ptr, ptr %0, align 8, !tbaa !7
  br label %96

96:                                               ; preds = %.lr.ph49, %96
  %97 = phi i64 [ %91, %.lr.ph49 ], [ %105, %96 ]
  %98 = phi i64 [ 0, %.lr.ph49 ], [ %99, %96 ]
  %99 = add nuw nsw i64 %98, 1
  %100 = getelementptr i32, ptr %12, i64 %98
  %101 = load i32, ptr %100, align 4, !tbaa !3
  %102 = add nsw i64 %92, %98
  %103 = mul i64 %94, %102
  %104 = getelementptr i8, ptr %95, i64 %103
  store i32 %101, ptr %104, align 4, !tbaa !3
  %105 = add nsw i64 %97, -1
  %106 = icmp ugt i64 %97, 1
  br i1 %106, label %96, label %._crit_edge50

._crit_edge50:                                    ; preds = %96, %.loopexit
  tail call void @free(ptr %12)
  ret void
}

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: readwrite)
define void @_QFPswap(ptr nocapture %0, ptr nocapture %1) local_unnamed_addr #3 {
  %3 = load i32, ptr %0, align 4, !tbaa !3
  %4 = load i32, ptr %1, align 4, !tbaa !3
  store i32 %4, ptr %0, align 4, !tbaa !3
  store i32 %3, ptr %1, align 4, !tbaa !3
  ret void
}

declare ptr @_FortranAioBeginExternalListInput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioInputInteger(ptr, ptr, i32) local_unnamed_addr

declare i32 @_FortranAioEndIoStatement(ptr) local_unnamed_addr

declare i1 @_FortranAioInputDescriptor(ptr, ptr) local_unnamed_addr

declare ptr @_FortranAioBeginExternalListOutput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioOutputInteger32(ptr, i32) local_unnamed_addr

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i64 @llvm.smax.i64(i64, i64) #4

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smax.i32(i32, i32) #4

attributes #0 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #1 = { mustprogress nounwind willreturn allockind("free") memory(argmem: readwrite, inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #2 = { nounwind }
attributes #3 = { mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: readwrite) }
attributes #4 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

!llvm.module.flags = !{!0, !1, !2}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{!4, !4, i64 0}
!4 = !{!"any data access", !5, i64 0}
!5 = !{!"any access", !6, i64 0}
!6 = !{!"Flang Type TBAA Root"}
!7 = !{!8, !8, i64 0}
!8 = !{!"descriptor member", !5, i64 0}
