:- module( _, [search/2], [assertions , regtypes , basicmodes , nativeprops] ).

search([[ref(loc(1)),num(int(A))],[array(1,[num(int(B))|_1])]],[num(int(1))]) :-
        A=<B,
        A\=B,
        A>B .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(C)),num(int(E))|D])]],[num(int(1))]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(C)),num(int(E))|D],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(C)),num(int(E))|D],num(int(K))),
        A\=K,
        0<B,
        A>C,
        1\=B,
        L is 0+B,
        1 is L//2,
        1<B,
        A=<E .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[E]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        M is L//2,
        0=<M,
        M<B,
        N is M+1,
        mynth(N,[num(int(D))|C],num(int(O))),
        A=<O,
        1\=M,
        P is 0+M,
        Q is P//2,
        0=<Q,
        Q<B,
        R is Q+1,
        mynth(R,[num(int(D))|C],num(int(S))),
        A=<S,
        execute_notrace_1(B,C,D,A,Q,_1,_2,_3,_4,_5,E,_6) .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[num(int(E))]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        E is L//2,
        0=<E,
        E<B,
        M is E+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A=<N,
        1\=E,
        O is 0+E,
        P is O//2,
        0=<P,
        P<B,
        Q is P+1,
        mynth(Q,[num(int(D))|C],num(int(R))),
        A>R,
        E is P+1 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[E]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        M is L//2,
        0=<M,
        M<B,
        N is M+1,
        mynth(N,[num(int(D))|C],num(int(O))),
        A=<O,
        1\=M,
        P is 0+M,
        Q is P//2,
        0=<Q,
        Q<B,
        R is Q+1,
        mynth(R,[num(int(D))|C],num(int(S))),
        A>S,
        T is Q+1,
        T\=M,
        U is Q+M,
        V is U//2,
        0=<V,
        V<B,
        W is V+1,
        mynth(W,[num(int(D))|C],num(int(X))),
        A=<X,
        execute_notrace_2(B,C,D,A,V,Q,_1,_2,_3,_4,_5,E,_6) .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[E]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        M is L//2,
        0=<M,
        M<B,
        N is M+1,
        mynth(N,[num(int(D))|C],num(int(O))),
        A=<O,
        1\=M,
        P is 0+M,
        Q is P//2,
        0=<Q,
        Q<B,
        R is Q+1,
        mynth(R,[num(int(D))|C],num(int(S))),
        A>S,
        T is Q+1,
        T\=M,
        U is Q+M,
        V is U//2,
        0=<V,
        V<B,
        W is V+1,
        mynth(W,[num(int(D))|C],num(int(X))),
        A>X,
        execute_notrace_4(B,C,D,A,V,M,_1,_2,_3,_4,_5,E,_6) .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A=<N,
        1\=L,
        O is 0+L,
        P is O//2,
        0=<P,
        P<B,
        Q is P+1,
        mynth(Q,[num(int(D))|C],num(int(R))),
        A>R,
        S is P+1,
        S\=L,
        T is P+L,
        U is T//2,
        U<0 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A=<N,
        1\=L,
        O is 0+L,
        P is O//2,
        0=<P,
        P<B,
        Q is P+1,
        mynth(Q,[num(int(D))|C],num(int(R))),
        A>R,
        S is P+1,
        S\=L,
        T is P+L,
        U is T//2,
        U>=B .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A=<N,
        1\=L,
        O is 0+L,
        P is O//2,
        P<0 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A=<N,
        1\=L,
        O is 0+L,
        P is O//2,
        P>=B .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[num(int(B))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A>N,
        B is L+1 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[E]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        M is L//2,
        0=<M,
        M<B,
        N is M+1,
        mynth(N,[num(int(D))|C],num(int(O))),
        A>O,
        P is M+1,
        P\=B,
        Q is M+B,
        R is Q//2,
        0=<R,
        R<B,
        S is R+1,
        mynth(S,[num(int(D))|C],num(int(T))),
        A=<T,
        execute_notrace_2(B,C,D,A,R,M,_1,_2,_3,_4,_5,E,_6) .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[E]) :-
        B\=0,
        F is B-1,
        0=<F,
        F<B,
        G is F+1,
        mynth(G,[num(int(D))|C],num(int(H))),
        A=<H,
        I is B-1,
        0=<I,
        I<B,
        J is I+1,
        mynth(J,[num(int(D))|C],num(int(K))),
        A\=K,
        0<B,
        A>D,
        1\=B,
        L is 0+B,
        M is L//2,
        0=<M,
        M<B,
        N is M+1,
        mynth(N,[num(int(D))|C],num(int(O))),
        A>O,
        P is M+1,
        P\=B,
        Q is M+B,
        R is Q//2,
        0=<R,
        R<B,
        S is R+1,
        mynth(S,[num(int(D))|C],num(int(T))),
        A>T,
        execute_notrace_4(B,C,D,A,R,B,_1,_2,_3,_4,_5,E,_6) .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A>N,
        O is L+1,
        O\=B,
        P is L+B,
        Q is P//2,
        Q<0 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        0=<L,
        L<B,
        M is L+1,
        mynth(M,[num(int(D))|C],num(int(N))),
        A>N,
        O is L+1,
        O\=B,
        P is L+B,
        Q is P//2,
        Q>=B .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        L<0 .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[refE(loc(2))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A>D,
        1\=B,
        K is 0+B,
        L is K//2,
        L>=B .
search([[ref(loc(1)),num(int(A))],[array(B,[num(int(D))|C])]],[num(int(0))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,[num(int(D))|C],num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,[num(int(D))|C],num(int(J))),
        A\=J,
        0<B,
        A=<D .
search([[ref(loc(1)),num(int(A))],[array(B,C)]],[refE(loc(2))]) :-
        B\=0,
        D is B-1,
        0=<D,
        D<B,
        E is D+1,
        mynth(E,C,num(int(F))),
        A=<F,
        G is B-1,
        0=<G,
        G<B,
        H is G+1,
        mynth(H,C,num(int(I))),
        A\=I,
        0>=B .
search([[ref(loc(1)),num(int(A))],[array(B,C)]],[num(int(D))]) :-
        B\=0,
        E is B-1,
        0=<E,
        E<B,
        F is E+1,
        mynth(F,C,num(int(G))),
        A=<G,
        H is B-1,
        0=<H,
        H<B,
        I is H+1,
        mynth(I,C,num(int(A))),
        D is B-1 .
search([[ref(loc(1)),num(int(A))],[array(B,C)]],[refE(loc(2))]) :-
        B\=0,
        D is B-1,
        0=<D,
        D<B,
        E is D+1,
        mynth(E,C,num(int(F))),
        A=<F,
        G is B-1,
        G<0 .
search([[ref(loc(1)),num(int(A))],[array(B,C)]],[refE(loc(2))]) :-
        B\=0,
        D is B-1,
        0=<D,
        D<B,
        E is D+1,
        mynth(E,C,num(int(F))),
        A=<F,
        G is B-1,
        G>=B .
search([[ref(loc(1)),num(int(A))],[array(B,C)]],[num(int(B))]) :-
        B\=0,
        D is B-1,
        0=<D,
        D<B,
        E is D+1,
        mynth(E,C,num(int(F))),
        A>F .
search([[ref(loc(1)),num(int(_1))],[array(A,_2)]],[refE(loc(2))]) :-
        A\=0,
        B is A-1,
        B<0 .
search([[ref(loc(1)),num(int(_1))],[array(A,_2)]],[refE(loc(2))]) :-
        A\=0,
        B is A-1,
        B>=A .
search([[ref(loc(1)),num(int(_1))],[array(0,_2)]],[num(int(0))]).
search([[null,num(int(_1))],[]],[refE(loc(1))]).

execute_notrace_1(A,B,C,_1,1,[array(A,[num(int(C))|B])],_2,_3,_4,_5,num(int(1)),[]).
execute_notrace_1(A,B,C,D,E,F,G,H,I,J,K,L) :-
        1\=E,
        M is 0+E,
        N is M//2,
        0=<N,
        N<A,
        O is N+1,
        mynth(O,[num(int(C))|B],num(int(P))),
        D=<P,
        execute_notrace_1(A,B,C,D,N,F,G,H,I,J,K,L) .
execute_notrace_1(A,B,C,D,E,[array(A,[num(int(C))|B])],_1,_2,_3,_4,num(int(E)),[]) :-
        1\=E,
        F is 0+E,
        G is F//2,
        0=<G,
        G<A,
        H is G+1,
        mynth(H,[num(int(C))|B],num(int(I))),
        D>I,
        E is G+1 .
execute_notrace_1(A,B,C,D,E,F,G,H,I,J,K,L) :-
        1\=E,
        M is 0+E,
        N is M//2,
        0=<N,
        N<A,
        O is N+1,
        mynth(O,[num(int(C))|B],num(int(P))),
        D>P,
        Q is N+1,
        Q\=E,
        R is N+E,
        S is R//2,
        0=<S,
        S<A,
        T is S+1,
        mynth(T,[num(int(C))|B],num(int(U))),
        D=<U,
        execute_notrace_2(A,B,C,D,S,N,F,G,H,I,J,K,L) .
execute_notrace_1(A,B,C,D,E,F,G,H,I,J,K,L) :-
        1\=E,
        M is 0+E,
        N is M//2,
        0=<N,
        N<A,
        O is N+1,
        mynth(O,[num(int(C))|B],num(int(P))),
        D>P,
        Q is N+1,
        Q\=E,
        R is N+E,
        S is R//2,
        0=<S,
        S<A,
        T is S+1,
        mynth(T,[num(int(C))|B],num(int(U))),
        D>U,
        execute_notrace_4(A,B,C,D,S,E,F,G,H,I,J,K,L) .
execute_notrace_1(A,B,C,D,E,[array(A,[num(int(C))|B]),[]],_1,_2,_3,_4,refE(loc(2)),[]) :-
        1\=E,
        F is 0+E,
        G is F//2,
        0=<G,
        G<A,
        H is G+1,
        mynth(H,[num(int(C))|B],num(int(I))),
        D>I,
        J is G+1,
        J\=E,
        K is G+E,
        L is K//2,
        L<0 .
execute_notrace_1(A,B,C,D,E,[array(A,[num(int(C))|B]),[]],_1,_2,_3,_4,refE(loc(2)),[]) :-
        1\=E,
        F is 0+E,
        G is F//2,
        0=<G,
        G<A,
        H is G+1,
        mynth(H,[num(int(C))|B],num(int(I))),
        D>I,
        J is G+1,
        J\=E,
        K is G+E,
        L is K//2,
        L>=A .
execute_notrace_1(A,B,C,_1,D,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        1\=D,
        E is 0+D,
        F is E//2,
        F<0 .
execute_notrace_1(A,B,C,_1,D,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        1\=D,
        E is 0+D,
        F is E//2,
        F>=A .

execute_notrace_2(A,B,C,_1,D,E,[array(A,[num(int(C))|B])],_2,_3,_4,_5,num(int(D)),[]) :-
        D is E+1 .
execute_notrace_2(A,B,C,D,E,F,G,H,I,J,K,L,M) :-
        N is F+1,
        N\=E,
        O is F+E,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D=<R,
        execute_notrace_2(A,B,C,D,P,F,G,H,I,J,K,L,M) .
execute_notrace_2(A,B,C,D,E,F,G,H,I,J,K,L,M) :-
        N is F+1,
        N\=E,
        O is F+E,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D>R,
        execute_notrace_3(A,B,C,D,P,E,P,G,H,I,J,K,L,M) .
execute_notrace_2(A,B,C,_1,D,E,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        F is E+1,
        F\=D,
        G is E+D,
        H is G//2,
        H<0 .
execute_notrace_2(A,B,C,_1,D,E,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        F is E+1,
        F\=D,
        G is E+D,
        H is G//2,
        H>=A .

execute_notrace_3(A,B,C,_1,_2,D,E,[array(A,[num(int(C))|B])],_3,_4,_5,_6,num(int(D)),[]) :-
        D is E+1 .
execute_notrace_3(A,B,C,D,_1,E,F,G,H,I,J,K,L,M) :-
        N is F+1,
        N\=E,
        O is F+E,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D=<R,
        execute_notrace_2(A,B,C,D,P,F,G,H,I,J,K,L,M) .
execute_notrace_3(A,B,C,D,_1,E,F,G,H,I,J,K,L,M) :-
        N is F+1,
        N\=E,
        O is F+E,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D>R,
        execute_notrace_3(A,B,C,D,P,E,P,G,H,I,J,K,L,M) .
execute_notrace_3(A,B,C,_1,_2,D,E,[array(A,[num(int(C))|B]),[]],_3,_4,_5,_6,refE(loc(2)),[]) :-
        F is E+1,
        F\=D,
        G is E+D,
        H is G//2,
        H<0 .
execute_notrace_3(A,B,C,_1,_2,D,E,[array(A,[num(int(C))|B]),[]],_3,_4,_5,_6,refE(loc(2)),[]) :-
        F is E+1,
        F\=D,
        G is E+D,
        H is G//2,
        H>=A .

execute_notrace_4(A,B,C,_1,D,E,[array(A,[num(int(C))|B])],_2,_3,_4,_5,num(int(E)),[]) :-
        E is D+1 .
execute_notrace_4(A,B,C,D,E,F,G,H,I,J,K,L,M) :-
        N is E+1,
        N\=F,
        O is E+F,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D=<R,
        execute_notrace_2(A,B,C,D,P,E,G,H,I,J,K,L,M) .
execute_notrace_4(A,B,C,D,E,F,G,H,I,J,K,L,M) :-
        N is E+1,
        N\=F,
        O is E+F,
        P is O//2,
        0=<P,
        P<A,
        Q is P+1,
        mynth(Q,[num(int(C))|B],num(int(R))),
        D>R,
        execute_notrace_4(A,B,C,D,P,F,G,H,I,J,K,L,M) .
execute_notrace_4(A,B,C,_1,D,E,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        F is D+1,
        F\=E,
        G is D+E,
        H is G//2,
        H<0 .
execute_notrace_4(A,B,C,_1,D,E,[array(A,[num(int(C))|B]),[]],_2,_3,_4,_5,refE(loc(2)),[]) :-
        F is D+1,
        F\=E,
        G is D+E,
        H is G//2,
        H>=A .


