#include<bits/stdc++.h> using namespace std; struct Node{ int val; Node* left=NULL; Node *right = NULL; }; //最终分解为向左向右两种旋转 Node * LL(Node *root){ Node *head = root->left; root->left = head->right; head->right = root; return head; } Node * RR(Node *root){ Node *head = root->right; root->right = head->left; head->left = root; return head; } Node * LR(Node *root){ root->left = RR(root->left); return LL(root); } Node * RL(Node *root){ root->right = LL(root->right); return RR(root); } int getDepth(Node *root,int d){ if (!root)return d; return max(getDepth(root->left, d + 1), getDepth(root->right, d + 1)); } Node* InsertAVL(Node* root, Node* n){ if (!root){ root = n; }else if (n->val<root->val){ root->left = InsertAVL(root->left, n); if (getDepth(root->left,1) - getDepth(root->right,1) == 2) { if (n->val < root->left->val) root = LL(root); else root = LR(root); } }else if (n->val>root->val){ root->right = InsertAVL(root->right, n); if (getDepth(root->left, 1) - getDepth(root->right, 1) == -2) { if (n->val > root->right->val) root = RR(root); else root = RL(root); } } return root; } int main(){ int N; cin >> N; Node *root = new Node; cin >> root->val; for (int i = 1; i < N;i++){ Node *n = new Node; cin >> n->val; root=InsertAVL(root, n); } cout << root->val; return 0; }