// . O 〇 o #=# <- space station
// → ← → ←
//
// mass 1 5 7 3
// direction 1 -1 1 -1
//
// answer: 1

// . o O 〇 #=#
// → → → ←
//
// mass 1 3 5 7
// direction 1 1 1 -1
//
// answer: 0

// O . o #=#
// → → ←
//
// mass 5 1 4
// direction 1 1 -1
//
// answer: 1

// . O o #=#
// → → ←
//
// mass 1 5 4
// direction 1 1 -1
//
// answer: 2
// "static void main" must be defined in a public class.
public class Main {
    static class Asteroid{
        private int mass;
        private int direction;

        Asteroid(int mass, int direction) {
            this.mass = mass;
            this.direction = direction;
        }

        private int getMass() {
            return mass;
        }

        private int getDirection() {
            return direction;
        }
    }

    public static void main(String[] args) {
        Asteroid[] case1 = new Asteroid[]{
            new Asteroid(1, 1),
            new Asteroid(5, -1),
            new Asteroid(7, 1),
            new Asteroid(3, -1),
        };

        Asteroid[] case2 = new Asteroid[]{
            new Asteroid(1, 1),
            new Asteroid(3, 1),
            new Asteroid(5, 1),
            new Asteroid(7, -1),
        };

        Asteroid[] case3 = new Asteroid[]{
            new Asteroid(5, 1),
            new Asteroid(1, 1),
            new Asteroid(4, -1),
        };

        Asteroid[] case4 = new Asteroid[]{
            new Asteroid(1, 1),
            new Asteroid(5, 1),
            new Asteroid(4, -1),
        };

        testCase(1, case1, 1);
        testCase(2, case2, 0);
        testCase(3, case3, 1);
        testCase(4, case4, 2);
    }

    private static void testCase(int testCase, Asteroid[] asteroids, int expected) {
        int actual = countHits(asteroids);
        if (actual == expected) {
            System.out.println("Case " + testCase + ": PASSED");
        } else {
            System.out.println("Case " + testCase + ": FAILED; got " + actual + " expected " + expected);
        }
    }

    /*
        iterate over asteroids      O(n)
            if asteroid is moving away AWAY
                iterate backwards   FORWARDS        O(n)
                    if AWAY.mass > FORWARDS.mass
                        remove forwards from array  O(n)
                    else
                        remove away from array  O(n)
                        and stop iterating
        return size of remaining array

        O(n^3) O(1) space

        optimize

        // o . 0 #=#
        // ← → →
        // 4 1 5
        answer : 2
        no sorting!

        dump into linked list to resize array
        O(n^2) O(n) space
        O(n^2) time O(1) space

     */
    private static int countHits(Asteroid[] asteroids) {
        return 0;
    }
}