class Solution {

  /**
    * @param Integer[] $nums
    * @return Integer
    */
    function waysToMakeFair($nums) {
        $len = count($nums);
        $ans = 0;

        $leftOdd = 0;
        $rightOdd = 0;
        $leftEven = 0;
        $rightEven = 0;

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven += $nums[$i];
            else
                $rightOdd += $nums[$i];
        }

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven -= $nums[$i];
            else
                $rightOdd -= $nums[$i];

            if ($leftEven + $rightOdd === $rightEven + $leftOdd) $ans++;

            if ($i%2 === 0)
                $leftEven += $nums[$i];
            else
                $leftOdd += $nums[$i];
        }

        return $ans;
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const brackets = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (i=0; i<s.length; i++) {
        if (s.length === 0) return true;

        const c = s[i];
        if (brackets[c]) {
            stack.push(c);
        } else {
            const lastBracket = stack.pop();
            if (brackets[lastBracket] !== c) return false;
        }
    }

    if (stack.length > 0) return false;

    return true;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    s = processString(s);
    t = processString(t);
    //console.log({s, t})
    return s===t;
};

let processString = function(s) {
    const a = [];
    let skip = 0;
    for (let i = s.length-1; i >= 0; i--) {
        if (s[i] === '#') {
            skip++;
        } else if (skip > 0) {
            skip--;
        } else {
            a.push(s[i]);
        }
        //console.log({a, skip, i})
    }
    let re = '';
    //console.log({ a: a.length})
    while (a.length > 0) {
        re += a.pop();
        //console.log({i, re, a: a.length})
    }
    return re;
}

/**
* Definition for Employee.
* class Employee {
*     public $id = null;
*     public $importance = null;
*     public $subordinates = array();
*     function __construct($id, $importance, $subordinates) {
*         $this->id = $id;
*         $this->importance = $importance;
*         $this->subordinates = $subordinates;
*     }
* }
*/

class Solution {
/**
 * @param Employee[] $employees
 * @param Integer $id
 * @return Integer
 */

function getImportance($employees, $id) {
  if (empty($employees)) return 0;
  $emap = [];
  foreach ($employees as $e) {
    $emap[$e->id] = $e;
  }

  return $this->recurse($emap, $id);
 }

function recurse($emap, $id) {
  $e = $emap[$id];
  $ans = $e->importance;
  foreach ($e->subordinates as $sub) {
    $ans += $this->recurse($emap, $sub);
  }
  return $ans;
 }
}

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    const stack = [];
    const charArray = s.split("");
    const rightBracketsToRemove = [];

    for (let i=0;i<charArray.length;i++) {
        if (charArray[i] === '(') {
            stack.push(i);
        } else if (charArray[i] === ')' && stack.length > 0) {
            stack.pop();
        } else if (charArray[i] === ')') {
            charArray[i] = '';
        }
    }

    while (stack.length > 0) {
        const i = stack.pop();
        charArray[i] = '';
    }

    return charArray.join('');
};

    private $v = ['M' = > 1000, 'D' = > 500, 'C' = > 100, 'L' = > 50, 'X' = > 10, 'V' = > 5, 'I' = > 1];
  /**
    * @param String $s
    * @return Integer
    */
    function romanToInt($s) {
        $n = 0;
        $last = '';
        for ($i=0;$i < strlen  ($s  );   $i++)   {
             $n   +=   $this-  >v[$s[$i]];
            if (($s[$i] == 'V' || $s[$i] == 'X')  &&  $last == 'I') {
                $n = $n - 2;
            } elseif (($s[$i] == 'L' || $s[$i] == 'C')  &&  $last == 'X') {
                $n -= 20;
            } elseif (($s[$i] == 'D' || $s[$i] == 'M')  &&  $last == 'C') {
                $n -= 200;
            }
            $last = $s[$i];
        }

        return $n;
    }
}