list_to_bag([], []).
list_to_bag([A|T],B):-
  list_to_bag(T,B1),
  add_to_list(A,B1,B).

add_to_list(A, [A-N|T], [A-N1|T]):-
  N1 is N+1.
add_to_list(A, [], [A-1]).
add_to_list(A, [B-N|T], [B-N|T1]):-
  A \= B,
  add_to_list(A,T,T1).

union([], [], []).
union([], [H|Tl], [H|Tl]).
union([H|Tl], [], [H|Tl]).
union([E-M|Tl], B, C):-
  B\=[],
  ( select(E-M1, B, B1) -> M2 is max(M,M1),
    C=[E-M2|C1]
  ; C=[E-M|C1], B1=B
  ),
  union(Tl, B1, C1).

intersection([], [], []).
intersection([], [_|_], []).
intersection([_|_], [], []).
intersection([E-M|Tl], B, C):-
  B\=[],
  ( select(E-M1, B, B1) -> M2 is min(M,M1),
    C=[E-M2|C1]
  ; C=C1, B1=B
  ),
  intersection(Tl, B1, C1).

zigzag([]).
zigzag([_]).
zigzag([_,_]).
zigzag([A,B,C|Tl]):-
  ( A<B, B>C
  ; A>B, B<C
  ),
  zigzag([B,C|Tl]).

zigzag_count([], 0).
zigzag_count([_], 0).
zigzag_count([_,_], 0).
zigzag_count([A,B,C|Tl], N):-
  zigzag_count([B,C|Tl], N1),
  ( A<B, B>C -> N is N1 + 1
  ; A>B, B<C -> N is N1 + 1
  ; N is N1
  ).

ordered_tree(Tree):-
  ordered_tree(Tree,0,_).

ordered_tree(leaf(V),Max,V):-
  V > Max.
ordered_tree(node(L,R),Max,Max2):-
  ordered_tree(L,Max,Max1),
  ordered_tree(R,Max1,Max2).

tree_leftmost_value(leaf(V), V).
tree_leftmost_value(node(L,_), V):-
  tree_leftmost_value(L,V).

tree_rightmost_value(leaf(V), V).
tree_rightmost_value(node(_,R), V):-
  tree_rightmost_value(R,V).

ordered_tree2(leaf(_)).
ordered_tree2(node(L,R)):-
  ordered_tree(L),
  ordered_tree(R),
  tree_leftmost_value(R,Min),
  tree_rightmost_value(L,Max),
  Max < Min.