description: On an endless checkered sheet of paper, n cells are chosen and colored in three colors, where n is divisible by 3. It turns out that there are exactly n/3 marked cells of each of three colors! 
  
  Find the largest such k that it's possible to choose k/3 cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:
  
    * No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be 0.
    * The i-th rectangle contains all the chosen cells of the i-th color and no chosen cells of other colors, for i = 1, 2, 3. 
  
  Input
  
  The first line of the input contains a single integer n — the number of the marked cells (3 ≤ n ≤ 10^5, n is divisible by 3).
  
  The i-th of the following n lines contains three integers x_i, y_i, c_i (|x_i|,|y_i| ≤ 10^9; 1 ≤ c_i ≤ 3), where (x_i, y_i) are the coordinates of the i-th marked cell and c_i is its color.
  
  It's guaranteed that all cells (x_i, y_i) in the input are distinct, and that there are exactly n/3 cells of each color.
  
  Output
  
  Output a single integer k — the largest number of cells you can leave.
  
  Examples
  
  Input
  
  
  9
  2 3 1
  4 1 2
  2 1 3
  3 4 1
  5 3 2
  4 4 3
  2 4 1
  5 2 2
  3 5 3
  
  
  Output
  
  
  6
  
  
  Input
  
  
  3
  1 1 1
  2 2 2
  3 3 3
  
  
  Output
  
  
  3
  
  Note
  
  In the first sample, it's possible to leave 6 cells with indexes 1, 5, 6, 7, 8, 9.
  
  In the second sample, it's possible to leave 3 cells with indexes 1, 2, 3.
solution: #include <bits/stdc++.h>
  using namespace std;
  struct colorcount_t {
    int many[3];
    colorcount_t() {
      for (int i = 0; i < 3; ++i) many[i] = 0;
    }
  };
  struct separator_t {
    struct query_t {
      int low, high;
      int many_low, many_high;
      map<int, colorcount_t>::iterator it;
      void update(map<int, colorcount_t> &counts) {
        while (many_low > many_high && it != counts.begin()) {
          --it;
          many_low -= it->second.many[low];
          many_high += it->second.many[high];
        }
        while (many_low < many_high && it != counts.end()) {
          many_high -= it->second.many[high];
          many_low += it->second.many[low];
          ++it;
        }
        if (it != counts.begin()) {
          auto it2 = it;
          --it2;
          int many_low2 = many_low - it2->second.many[low];
          int many_high2 = many_high + it2->second.many[high];
          if (min(many_low2, many_high2) > result()) {
            it = it2;
            many_low = many_low2;
            many_high = many_high2;
          }
        }
      }
      int result() const { return min(many_low, many_high); }
    };
    vector<query_t> queries;
    map<int, colorcount_t> counts;
    separator_t() {
      for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
          if (i != j) queries.push_back({i, j, 0, 0, counts.end()});
    }
    void add(int pos, int added_color) {
      counts[pos].many[added_color] += 1;
      for (query_t &q : queries) {
        if (q.it == counts.end() || pos < q.it->first) {
          if (q.low == added_color) q.many_low += 1;
        } else {
          if (q.high == added_color) q.many_high += 1;
        }
        q.update(counts);
      }
    }
  };
  int main() {
    int n;
    scanf("%d", &n);
    struct point_t {
      int x, y, c;
    };
    vector<point_t> points(n);
    for (int i = 0; i < n; ++i)
      scanf("%d %d %d", &points[i].x, &points[i].y, &points[i].c), --points[i].c;
    int result = 0;
    for (int rep = 0; rep < 2; ++rep) {
      colorcount_t cc;
      for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
      sort(points.begin(), points.end(),
           [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
      separator_t sep;
      for (int i = 0, j = i; i != n; i = j) {
        while (j != n && points[j].x == points[i].x) ++j;
        for (int k = i; k < j; ++k) {
          sep.add(points[k].x, points[k].c);
          cc.many[points[k].c] -= 1;
        }
        for (const separator_t::query_t &q : sep.queries) {
          int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
          int res = min(q.result(), cc.many[other]);
          result = max(result, res);
        }
      }
      for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
    }
    for (int rep1 = 0; rep1 < 2; ++rep1) {
      for (int rep2 = 0; rep2 < 2; ++rep2) {
        colorcount_t cc;
        for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
        sort(
            points.begin(), points.end(),
            [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
        separator_t sep;
        for (int i = 0, j = i; i != n; i = j) {
          while (j != n && points[j].x == points[i].x) ++j;
          for (int k = i; k < j; ++k) {
            sep.add(points[k].y, points[k].c);
            cc.many[points[k].c] -= 1;
          }
          for (const separator_t::query_t &q : sep.queries) {
            int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
            int res = min(q.result(), cc.many[other]);
            result = max(result, res);
          }
        }
        for (int i = 0; i < n; ++i) points[i].x = -points[i].x;
      }
      for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
    }
    printf("%d\n", result * 3);
    return 0;
  }
  