#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n, m;
  cin >> n >> m;

  vector<pair<pair<int,int>, int> > v;
  rep(i, m) {
      int a, b;
      cin >> a >> b;
      v.push_back(mp(mp(a, b), i));
  }

  sort(v.begin(), v.end());

  vector<int> e;
  vector<P> q;
  vector<pair<int,pair<int,int> > > ans;
  int t = 0;
  rep(i, m) {
      int cost = v[i].first.first;
      int f = v[i].first.second;
      int j = v[i].second;

      if(f == 1) {
          e.push_back(cost);
          ans.push_back(mp(j, mp(t, t+1)));
          t++;
      }
      else if(f == 0) {
          q.push_back(mp(cost, j));
      }
  }

  bool flag = true;
  int from = 0, to = 1;
  for(int i = 0; i < q.size(); i++) {
      if(to == e.size()) {
          flag = false;
          break;
      }

      if(e[from] <= q[i].first && e[to] <= q[i].first) {
          ans.push_back(mp(q[i].second, mp(from, to+1) ));
      } else {
          P p = q.back();
          if(e[from] <= p.first && e[to] <= p.first) {
              ans.push_back(mp(p.second, mp(from, to+1)));
              q.pop_back();
          }
          i--;
      }

      if(from == to - 1) {
          from = 0;
          to++;
      } else {
          from++;
      }
  }

  if(flag) {
      sort(ans.begin(), ans.end());
      rep(i, ans.size()) {
          cout << ans[i].second.first+1 << " " << ans[i].second.second+1 << endl;
      }
  } else {
      cout << -1 << endl;
  }

  return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  string s;
  cin >> s;

  int cnt = 0;
  bool flag = true;

  if(s[0] == '1') cnt++;

  rep(i, n) {
      if(flag) {
          if(s[i] == '1') continue;
          else {
              cnt++;
              flag = false;
          }
      } else {
          if(s[i] == '1') {
              cnt++;
              flag = true;
          } else continue;
      }
  }

  if(cnt + 2 <= n) cout << cnt + 2 << endl;
  else if(cnt + 1 <= n) cout << cnt + 1 << endl;
  else cout << cnt << endl;

  return 0;
}

720 + (10 ** 18 - 10000) / 2600 * 300
=> 115384615384614720
(10 ** 18 - 10000) % 2600
=> 2000

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = { 0, 1, 0, -1};

vector< int > v[5005][5005];
const int GETA = 1000;
int N = 0;

void dfs(int y, int x, int dir, int c) {
  if(c == N) return;

  int n = v[y][x].size();
  v[y][x].push_back(c);

  int ndir = 0;
  if(n % 2 == 0) {
      ndir = (dir + 1) % 4;
  } else {
      ndir = (dir + 3) % 4;
  }

  int ny = y + dy[ndir];
  int nx = x + dx[ndir];

  dfs(ny, nx, ndir, c+1);
  return;
}

void print(int x) {
  REP(i, GETA-x, GETA+x+1) {
      REP(j, GETA-x, GETA+x+1) {
          cout << v[i][j].size() << " ";
      }
      cout << endl;
  }
}

void print2(int x) {
  REP(i, GETA-x, GETA+x+1) {
      REP(j, GETA-x, GETA+x+1) {
          if(v[i][j].size() % 2 == 0) {
              cout << " ";
          } else {
              cout << "O";
          }
      }
      cout << endl;
  }
}

int main() {
  vector<int> t;
  rep(k, 10) {
      N = k * 100 + 10000;
      rep(i, 2005) rep(j, 2005) v[i][j].clear();
      dfs(GETA, GETA, 0, 0);
  
      ll cnt = 0;
      rep(i, 5005) {
          rep(j, 5005) {
              if(v[i][j].size() % 2 == 1) {
                  cnt++;
              }
          }
      }
  
      t.push_back(cnt);
      cout << cnt << endl;
  }
  
  rep(i, t.size()-1) {
      cout << t[i+1] - t[i] << " ";
  }
  cout << endl;

  return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  vector<int> v(n), t(n);
  rep(i, n) {
      cin >> v[i];
      t[i] = v[i];
  }

  sort(t.begin(), t.end());
  int ans = 0;
  map<int, int> m;

  rep(i, n) {
      if(m[v[i]] == -1) {
          m.erase(v[i]);
      } else {
          m[v[i]]++;
      }

      if(m[t[i]] == 1) {
          m.erase(t[i]);
      } else {
          m[t[i]]--;
      }

      if(m.size() == 0) {
          ans++;
      }
  }

  cout << ans << endl;

  return 0;
}