#include <chrono>
#include <iostream>
#include <random>
using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
// sum, left, right, value, prior, first_elem,
//  last_elem, add, assign, sz, is_assign, reversed, non_incr, non_decr,
struct Node {
  long long sum;
  Node* left = nullptr;
  Node* right = nullptr;
  int value;
  int prior;
  int first_elem, last_elem;
  int add = 0;
  int assign = 0;
  int sz = 1;
  bool is_assign = false;
  bool reversed = false, non_incr = true, non_decr = true;

  explicit Node(int elem)
      //      : value(elem),
      //        prior(rnd()),
      //        sum(elem),
      //        first_elem(elem),
      //        last_elem(elem) {}
      : sum(elem),
        value(elem),
        prior(rnd()),
        first_elem(elem),
        last_elem(elem) {}
  Node() : Node(0) {}
};

const int cVv5 = 100010;

Node nodes[cVv5];
int iindex = 0;

class Treap {
 private:
  mutable Node* root_ = nullptr;

  static void Merge(Node*& node, Node* left, Node* right) {
    Push(left, 0);
    Push(right, 0);
    if ((left == nullptr) || (right == nullptr)) {
      node = (left != nullptr) ? left : right;
    } else if (left->prior > right->prior) {
      Merge(left->right, left->right, right);
      node = left;
    } else {
      Merge(right->left, left, right->left);
      node = right;
    }
    FixNode(node);
  }

  static void Split(Node* node, Node*& left, Node*& right, int pos,
                    int tree_begin) {
    if (node == nullptr) {
      left = right = nullptr;
      return;
    }
    Push(node, 0);
    int val_pos = tree_begin + Size(node->left);
    if (pos <= val_pos) {
      Split(node->left, left, node->left, pos, tree_begin);
      right = node;
      FixNode(right);
    } else {
      Split(node->right, node->right, right, pos, val_pos + 1);
      left = node;
      FixNode(left);
    }
  }

  static void Push(Node* node, int depth = 1) {
    if (node == nullptr) {
      return;
    }
    if (node->is_assign) {
      node->value = node->first_elem = node->last_elem = node->assign;
      node->sum = node->value * node->sz;
      if (node->left != nullptr) {
        node->left->add = 0;
        node->left->is_assign = true;
        node->left->assign = node->value;
      }
      if (node->right != nullptr) {
        node->right->add = 0;
        node->right->is_assign = true;
        node->right->assign = node->value;
      }
      node->is_assign = false;
    }
    if (node->left != nullptr) {
      node->left->add += node->add;
    }
    if (node->right != nullptr) {
      node->right->add += node->add;
    }
    node->value += node->add;
    node->first_elem += node->add;
    node->last_elem += node->add;
    node->sum += node->add * node->sz;
    node->add = 0;

    if (node->reversed) {
      swap(node->left, node->right);
      swap(node->first_elem, node->last_elem);
      swap(node->non_decr, node->non_incr);
      node->reversed = false;
      if (node->left != nullptr) {
        node->left->reversed ^= 1;
      }
      if (node->right != nullptr) {
        node->right->reversed ^= 1;
      }
    }

    if (depth > 0) {
      Push(node->left, depth - 1);
      Push(node->right, depth - 1);
    }
  }

  static int Size(Node* node) { return (node != nullptr) ? node->sz : 0; }

  static long long Summa(Node* node) {
    return (node != nullptr) ? node->sum : 0LL;
  }

  static void FixNode(Node* node) {
    if (node == nullptr) {
      return;
    }
    Push(node);
    node->sz = 1 + Size(node->left) + Size(node->right);
    node->sum = node->value + Summa(node->left) + Summa(node->right);

    node->first_elem =
        (node->left != nullptr) ? node->left->first_elem : node->value;
    node->last_elem =
        (node->right != nullptr) ? node->right->last_elem : node->value;

    node->non_incr = node->non_decr = true;
    if (node->left != nullptr) {
      if (!node->left->non_incr || node->value > node->left->last_elem) {
        node->non_incr = false;
      }
      if (!node->left->non_decr || node->value < node->left->last_elem) {
        node->non_decr = false;
      }
    }
    if (node->right != nullptr) {
      if (!node->right->non_incr || node->value < node->right->first_elem) {
        node->non_incr = false;
      }
      if (!node->right->non_decr || node->value > node->right->first_elem) {
        node->non_decr = false;
      }
    }
  }

  static int FindStartLnis(Node* node, int tree_end, bool less) {
    Push(node, 0);
    if ((node == nullptr) || (node->non_incr && less) ||
        (node->non_decr && !less)) {
      return tree_end - Size(node);
    }
    Push(node->left, 0);
    Push(node->right, 0);
    int k = FindStartLnis(node->right, tree_end, less);
    int val_pos = tree_end - Size(node->right);
    if ((node->right == nullptr) ||
        (less && k == val_pos && node->right->first_elem <= node->value) ||
        (!less && k == val_pos && node->right->first_elem >= node->value)) {
      --k;
    }
    if ((node->left != nullptr) && k == val_pos - 1 &&
        ((less && node->left->last_elem >= node->value) ||
         (!less && node->left->last_elem <= node->value))) {
      k = FindStartLnis(node->left, val_pos - 1, less);
    }
    return k;
  }

  static int FindNln(Node* node, int x, int tree_begin, bool less) {
    while (node != nullptr) {
      Push(node, 0);
      if ((less && node->value > x) || (!less && node->value < x)) {
        node = node->left;
      } else {
        tree_begin += Size(node->left) + 1;
        node = node->right;
      }
    }
    return tree_begin;
  }

 public:
  Treap() = default;

  void Insert(int key, int value) {
    pair<Node*, Node*> res;
    Split(root_, res.first, res.second, key, 0);
    Node* new_node = &nodes[iindex++];
    new_node->sum = new_node->first_elem = new_node->last_elem =
        new_node->value = value;
    Merge(root_, res.first, new_node);
    Merge(root_, root_, res.second);
  }

  void Erase(int key) {
    pair<Node*, Node*> res;
    pair<Node*, Node*> tmp;
    Split(root_, res.first, res.second, key, 0);
    Split(res.second, tmp.first, tmp.second, 1, 0);
    Merge(root_, res.first, tmp.second);
  }

  void Add(int l, int r, int up) {
    if (l > r || up == 0) {
      return;
    }
    pair<Node*, Node*> first;
    pair<Node*, Node*> second;
    Split(root_, first.first, first.second, r + 1, 0);
    Split(first.first, second.first, second.second, l, 0);

    Push(second.second, 0);
    if (second.second != nullptr) {
      second.second->add += up;
    }

    Merge(root_, second.first, second.second);
    Merge(root_, root_, first.second);
  }

  void Assign(int l, int r, int up) {
    if (l > r) {
      return;
    }
    pair<Node*, Node*> first;
    pair<Node*, Node*> second;
    Split(root_, first.first, first.second, r + 1, 0);
    Split(first.first, second.first, second.second, l, 0);

    Push(second.second, 0);
    if (second.second != nullptr) {
      second.second->assign = up;
      second.second->is_assign = true;
    }

    Merge(root_, second.first, second.second);
    Merge(root_, root_, first.second);
  }

  [[nodiscard]] long long GetSum(int l, int r) {
    if (l > r) {
      return 0LL;
    }
    pair<Node*, Node*> first;
    pair<Node*, Node*> second;
    Split(root_, first.first, first.second, r + 1, 0);
    Split(first.first, second.first, second.second, l, 0);

    Push(second.second, 0);
    long long res = (second.second != nullptr) ? second.second->sum : 0LL;

    Merge(root_, second.first, second.second);
    Merge(root_, root_, first.second);
    return res;
  }

 private:
  static void NextPermutation(int l, int r, Node* node) {
    Node* left;
    Node* right;
    Split(node, node, right, r + 1, 0);

    int k = FindStartLnis(node, r, true) + 1;
    Split(node, left, node, max(l, k), 0);

    node->reversed ^= 1;
    if (l < k) {
      Node* between;
      Node* swap2;
      Node* swap1;
      Split(left, left, swap1, k - 1, 0);
      int nln = FindNln(node, swap1->value, k, true);
      Split(node, between, node, nln, k);
      Split(node, swap2, node, nln + 1, nln);
      Merge(node, swap1, node);
      Merge(node, between, node);
      Merge(node, swap2, node);
    }
    Merge(node, left, node);
    Merge(node, node, right);
  }

 public:
  void NextPermutation(int l, int r) { NextPermutation(l, r, root_); }

 private:
  static void PrevPermutation(int l, int r, Node* node) {
    Node* left;
    Node* right;
    Split(node, node, right, r + 1, 0);

    int k = FindStartLnis(node, r, false) + 1;
    Split(node, left, node, max(l, k), 0);

    node->reversed ^= 1;
    if (l < k) {
      Node* between;
      Node* swap2;
      Node* swap1;
      Split(left, left, swap1, k - 1, 0);
      int nln = FindNln(node, swap1->value, k, false);
      Split(node, between, node, nln, k);
      Split(node, swap2, node, nln + 1, nln);
      Merge(node, swap1, node);
      Merge(node, between, node);
      Merge(node, swap2, node);
    }
    Merge(node, left, node);
    Merge(node, node, right);
  }

 public:
  void PrevPermutation(int l, int r) { PrevPermutation(l, r, root_); }

 private:
  static void Print(Node* node) {
    if (node == nullptr) {
      return;
    }
    Push(node, 0);
    Print(node->left);
    cout << node->value << ' ';
    Print(node->right);
  }

 public:
  void Print() const {
    Print(root_);
    cout << '\n';
  }

  friend int main();
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  Treap treap;
  for (int i = 0; i < n; ++i) {
    int value;
    cin >> value;
    treap.Insert(i, value);
  }

  const int cV6 = 6;
  const int cV7 = 7;

  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int op;
    cin >> op;
    if (op == 1) {
      int l;
      int r;
      cin >> l >> r;
      cout << treap.GetSum(l, r) << '\n';
    } else if (op == 2) {
      int x;
      int pos;
      cin >> x >> pos;
      treap.Insert(pos, x);
    } else if (op == 3) {
      int pos;
      cin >> pos;
      treap.Erase(pos);
    } else if (op == 4) {
      int x;
      int l;
      int r;
      cin >> x >> l >> r;
      treap.Assign(l, r, x);
    } else if (op == 5) {
      int x;
      int l;
      int r;
      cin >> x >> l >> r;
      treap.Add(l, r, x);
    } else if (op == cV6) {
      int l;
      int r;
      cin >> l >> r;
      treap.NextPermutation(l, r);
    } else if (op == cV7) {
      int l;
      int r;
      cin >> l >> r;
      treap.PrevPermutation(l, r);
    }
  }
  treap.Print();
}
Rewrite all recursion calls into loops. Don't touch the rest of the logic