IDENTIFICATION                   DIVISION.
PROGRAM-ID.                      ABC_088_B.
ENVIRONMENT                      DIVISION.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 INP    PIC X(600).
    01 maxlen PIC 9(3).
    01 cur    PIC 9(3)  VALUE 1.
    01 i      PIC 9(18).
    01 j      PIC 9(18).
    01 len    PIC 9(3).

    01 N      PIC 9(3).

    01 qary1.
        03 qary11 OCCURS 100.
            05 qary    PIC 9(3).

    01 qfirst PIC 9(3) VALUE 1.
    01 qlast  PIC 9(3).

    01 tmp    PIC 9(4).
    01 wrk    PIC 9(3).

    01 il     PIC 9(3).
    01 ig     PIC 9(3).

    01 alice  PIC 9(5) VALUE 0.
    01 bob    PIC 9(5) VALUE 0.

    01 X      PIC 9(5).
    01 R      PIC 9(5).

    01 ZS     PIC Z(5)9.
    01 ans    PIC X(5).

    01 DUMMY  PIC X(1).

    01 FLG    PIC 9(1).

PROCEDURE                        DIVISION.
MAIN.
    ACCEPT N.

    ACCEPT INP.

    MOVE N TO maxlen.

    PERFORM VARYING i FROM 1 BY 1 UNTIL maxlen < i

        PERFORM VARYING j FROM cur BY 1
            UNTIL INP(j:1) = SPACE
        END-PERFORM

        COMPUTE len = j - cur

        MOVE INP(cur:len) TO qary(i)

        COMPUTE cur = j + 1

    END-PERFORM.

    MOVE N TO qlast.

    PERFORM QSORT.

    MOVE 1 TO FLG.
    PERFORM UNTIL FLG = 0
        *> 次のブロックのサイズが２以上の時は再帰
        IF qfirst + 2 <= il THEN
            SUBTRACT 1 FROM il GIVING qlast
            PERFORM QSORT
        ELSE
            IF ig <= qlast - 2
                ADD 1 ig GIVING qfirst
                PERFORM QSORT
            ELSE
                MOVE 0 TO FLG
            END-IF
        END-IF
    END-PERFORM.

    PERFORM VARYING i FROM N BY -1 UNTIL i <= 0
        DIVIDE 2 INTO i GIVING X REMAINDER R
        IF R = 0 THEN
            ADD qary(i) TO alice
        ELSE
            ADD qary(i) TO bob
        END-IF
    END-PERFORM.

    SUBTRACT bob FROM alice.
    MOVE alice TO ZS.

    PERFORM UNANS.

    DISPLAY ans(1:FUNCTION STORED-CHAR-LENGTH(ans)).
    STOP RUN.

UNANS                            SECTION.
    UNSTRING
        ZS DELIMITED BY ALL SPACE
        INTO DUMMY ans
    END-UNSTRING.

QSORT                            SECTION.
*> qary   : 配列
*> qfirst : ブロックの最初のインデックス
*> qlast  : ブロックの最後のインデックス

    MOVE qfirst TO il    *> 前半のインデックス
    MOVE qlast TO ig     *> 後半のインデックス

    *> 「ある値」は両端の要素の平均値にする
    ADD qary(qfirst) qary(qlast) GIVING tmp
    DIVIDE 2 INTO tmp GIVING x

    *> 交換ループ
    *> 位置が逆になると終了
    PERFORM UNTIL ig <= il
        *> x より小さい要素は無視
        PERFORM UNTIL x <= qary(il)
            ADD 1 TO il
        END-PERFORM

        *> x より大きい要素は無視
        PERFORM UNTIL qary(ig) <= x
            SUBTRACT 1 FROM ig
        END-PERFORM

        *> 位置がちゃんとしているときは交換し、
        *> il と ig を１つずつ進める
        IF il < ig THEN
            MOVE qary(il) TO wrk
            MOVE qary(ig) TO qary(il)
            MOVE wrk TO qary(ig)
            ADD 1 TO il
            SUBTRACT 1 FROM ig
        END-IF
    END-PERFORM

    *> il = ig で終わった時は、
    *> ig < il になるようにする
    IF il = ig THEN
        IF qary(il) < x THEN
            ADD 1 TO il
        ELSE
            SUBTRACT 1 FROM ig
        END-IF
    END-IF.
