namespace DtoU_merge_sort {
  int TIME;
  vector<int> tmp;
  void solve(vector<int> &A) {
    int time1 = clock();
    for(int siz = 1; siz < A.size(); siz <<= 1) {
      for(int i = 0; (i + siz) < A.size(); i += siz*2) {
        ///// 该处 (i + siz - 1) 时也能通过该题
        int l = i, r = i + siz;
        int sl = i + siz - 1, sr = min(i + 2*siz - 1, (int)(A.size() - 1));
        while(l <= sl && r <= sr) {
          if(A[l] <= A[r]) tmp.push_back(A[l++]);
          else tmp.push_back(A[r++]);
        }
        while(l <= sl) tmp.push_back(A[l++]);
        while(r <= sr) tmp.push_back(A[r++]);
        for(int j = i; j <= min(i + 2*siz - 1, (int)(A.size() - 1)); j++) {
          A[j] = tmp[j - i];
        }
        tmp.clear();
      }
    }
    int time2 = clock();
    TIME = time2 - time1;
  }
}
\\\\\