import javafx.util.Pair;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

public class Tree implements Runnable {
    private Node root;
    private Node max;

    public static void main(String[] args) {
      new Thread(null, new Tree(), "", 64 * 1024 * 1024).start();
    }

    public void run() {
      try {
        Tree t = new Tree();
        t.create("src/data/input.txt");
        t.count();
        t.print("src/data/output.txt");
      } catch(IOException e) {
        System.out.println("error found");
      }
    }

    private Pair<Node, Node> findNode(long value) {
      Node current = root;
      Node parent = null;
      while (true) {
        if (value > current.value && current.right != null) {
          parent = current;
          current = current.right;
        } else if (value < current.value && current.left != null) {
          parent = current;
          current = current.left;
        } else if (value == current.value) {
          return new Pair<>(current, parent);
        } else {
          return null;
        }
      }
    }

    private Pair<Node, Node> findInsertion(Node current, Node parent) {
      while (current.left != null) {
        parent = current;
        current = current.left;
      }

      return new Pair<>(current, parent);
    }

    public void delete(String path) throws IOException {
      Scanner s = new Scanner(new File(path));
      delete(s.nextLong());
      s.close();
    }

    private void delete(long value) {
      Pair<Node, Node> found = findNode(value);
      if (found != null) {
        Node foundParent = found.getValue();
        Node foundCurrent = found.getKey();

        if (foundCurrent.left != null && foundCurrent.right != null) {
          Pair<Node, Node> insertion = findInsertion(foundCurrent.right, foundCurrent);
          Node insertionParent = insertion.getValue();
          Node insertionCurrent = insertion.getKey();

          if (insertionParent == foundCurrent) {
            if (foundCurrent == root) {
              root = insertionCurrent;
              if (foundCurrent.left != null) {
                root.left = foundCurrent.left;
              }
            } else {
              if (foundParent.left == foundCurrent) {
                foundParent.left = insertionCurrent;
              } else {
                foundParent.right = insertionCurrent;
              }
              insertionCurrent.left = foundCurrent.left;
            }
          } else {
            if (foundCurrent == root) {
              if (insertionCurrent.right != null) {
                if (insertionParent.right == insertionCurrent) {
                  insertionParent.right = insertionCurrent.right;
                } else {
                  insertionParent.left = insertionCurrent.right;
                }
              } else {
                if (insertionParent.right == insertionCurrent) {
                  insertionParent.right = null;
                } else {
                  insertionParent.left = null;
                }
              }
              root = insertionCurrent;
              insertionCurrent.left = foundCurrent.left;
              insertionCurrent.right = foundCurrent.right;
            } else {
              if (insertionCurrent.right != null) {
                if (insertionParent.left == insertionCurrent) {
                  insertionParent.left = insertionCurrent.right;
                } else {
                  insertionParent.right = insertionCurrent.right;
                }
              } else {
                if (insertionParent.left == insertionCurrent) {
                  insertionParent.left = null;
                } else {
                  insertionParent.right = null;
                }
              }

              if (foundParent.right == foundCurrent) {
                foundParent.right = insertionCurrent;
              } else {
                foundParent.left = insertionCurrent;
              }

              insertionCurrent.left = foundCurrent.left;
              insertionCurrent.right = foundCurrent.right;
            }

          }
        } else if (foundCurrent.left == null && foundCurrent.right == null) {
          if (foundCurrent != root) {
            if (foundParent.left == foundCurrent) {
              foundParent.left = null;
            } else {
              foundParent.right = null;
            }
          } else {
            root = null;
          }
        } else {
          if (foundCurrent != root) {
            if (foundParent.left == foundCurrent) {
              if (foundCurrent.left != null) {
                foundParent.left = foundCurrent.left;
              } else {
                foundParent.left = foundCurrent.right;
              }
            } else {
              if (foundCurrent.left != null) {
                foundParent.right = foundCurrent.left;
              } else {
                foundParent.right = foundCurrent.right;
              }
            }
          } else {
            if (foundCurrent.left != null) {
              root = foundCurrent.left;
            } else {
              root = foundCurrent.right;
            }
          }
        }
      }
    }

    public void create(String path) throws IOException {
      File file = new File(path);
      Scanner s = new Scanner(file);
      Scanner check = new Scanner(file);

      check.nextLine();
      if (check.nextLine().isEmpty()) {
        s.nextLine();
        s.nextLine();
      }
      check.close();

      if (s.hasNext() && root == null) {
        root = new Node(s.nextLong());
        max = root;
      }

      while (s.hasNext()) {
        long v = s.nextLong();
        Node insertPlace = findPlace(v);
        if (insertPlace != null) {
          insertPlace.addChild(v);
        }
      }

      s.close();
    }

    public void count() {
      count(root);
//      delete(max.value);
    }

    private void count(Node current) {
      if (current.left != null) {
        count(current.left);
      }
      if (current.right != null) {
        count(current.right);
      }

      current.count += 1;
      if (current.right != null) {
        current.count += current.right.count;
      }
      if (current.left != null) {
        current.count += current.left.count;
      }

      findMax(current);
    }

    private int findDifference(Node current) {
      if (current.left != null && current.right != null) {
        return Math.abs(current.left.count - current.right.count);
      } else if (current.left != null) {
        return current.left.count;
      } else if (current.right != null) {
        return current.right.count;
      }
      return 0;
    }

    private void findMax(Node current) {
      int currentDifference = findDifference(current);
      int maxDifference = findDifference(max);

      if (currentDifference > maxDifference) {
        max = current;
      } else if (currentDifference == maxDifference && current.value > max.value) {
        max = current;
      }
    }

    private Node findPlace(long value) {
      Node current = root;
      while (true) {
        if (value > current.value && current.right != null) {
          current = current.right;
        } else if (value < current.value && current.left != null) {
          current = current.left;
        } else if (value == current.value) {
          return null;
        } else {
          break;
        }
      }

      return current;
    }

    public void print(String path) throws IOException {
      FileWriter w = new FileWriter(path);
      print(root, w);
      w.close();
    }

    private void print(Node current, FileWriter w) throws IOException {
      w.write(current.toString());
      w.write("\n");

      if (current.left != null) {
        print(current.left, w);
      }
      if (current.right != null) {
        print(current.right, w);
      }
    }

    private class Node {
      private Node left;
      private Node right;
      private long value;
      private int count;

      public Node(long value) {
        this.value = value;
      }

      public void addChild(long value) {
        if (value > this.value) {
          right = new Node(value);
        } else if (value < this.value) {
          left = new Node(value);
        }
      }

      @Override
      public String toString() {
        return Long.toString(value) + ": " + count;
      }
    }
}