PAT – 第30页

L2-009. 抢红包-PAT团体程序设计天梯赛GPLT

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（<= 104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K N1 P1 … NK PK

其中K（0 <= K <= 20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（> 0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

分析：用结构体存储下每一个结点的id、收入、收到红包的总数，然后进行排序后输出

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int id, total, getnum;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.getnum != b.getnum)
        return a.getnum > b.getnum;
    else
        return a.id < b.id;
}
int main() {
    int n, k, a, b;
    scanf("%d", &n);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++) {
        v[i].id = i;
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d %d", &a, &b);
            v[a].total += b;
            v[a].getnum++;
            v[i].total -= b;
        }
    }
    sort(v.begin()+1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        double temp = (double)(v[i].total * 1.0 / 100);
        printf("%d %.2f\n", v[i].id, temp);
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int id, total, getnum;

};

bool cmp1(node a, node b) {

if(a.total != b.total)

return a.total > b.total;

else if(a.getnum != b.getnum)

return a.getnum > b.getnum;

else

return a.id < b.id;

}

int main() {

int n, k, a, b;

scanf("%d", &n);

vector<node> v(n + 1);

for(int i = 1; i <= n; i++) {

v[i].id = i;

scanf("%d", &k);

for(int j = 0; j < k; j++) {

scanf("%d %d", &a, &b);

v[a].total += b;

v[a].getnum++;

v[i].total -= b;

}

sort(v.begin()+1, v.end(), cmp1);

for(int i = 1; i <= n; i++) {

double temp = (double)(v[i].total * 1.0 / 100);

printf("%d %.2f\n", v[i].id, temp);

}

return 0;

}

L2-010. 排座位-PAT团体程序设计天梯赛GPLT（并查集）

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（<= 100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：“宾客1 宾客2 关系”，其中“关系”为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出“No problem”；如果他们之间并不是朋友，但也不敌对，则输出“OK”；如果他们之间有敌对，然而也有共同的朋友，则输出“OK but…”；如果他们之间只有敌对关系，则输出“No way”。

输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but…
No way

分析：朋友之间的关系用并查集解决，敌人之间的关系用enemy[a][b] = enemy[b][a] = 1解决，因为朋友之间的朋友也是朋友，是传递关系，而敌人的敌人不一定是敌人，所以只需要用一个二维数组即可标记。

#include <cstdio>
#include <vector>
using namespace std;
vector<int> fri;
int enemy[101][101];
int findfri(int x) {
    while(x != fri[x])
        x = fri[x];
    return x;
}
void Union(int a, int b) {
    int fria = findfri(a);
    int frib = findfri(b);
    if(fria != frib)
        fri[fria] = frib;
}
int main() {
    int n, m, k, a, b, c;
    scanf("%d %d %d", &n, &m, &k);
    fri.resize(n + 1);
    for(int i = 1; i <= n; i++)
        fri[i] = i;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if(c == 1)
            Union(a, b);
        else {
            enemy[a][b] = 1;
            enemy[b][a] = 1;
        }
    }
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        if(findfri(a) == findfri(b) && enemy[a][b] == 0)
            printf("No problem\n");
        else if(findfri(a) != findfri(b) && enemy[a][b] == 0)
            printf("OK\n");
        else if(findfri(a) == findfri(b) && enemy[a][b] == 1)
            printf("OK but...\n");
        else if(enemy[a][b] == 1)
            printf("No way\n");
    }
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<int> fri;

int enemy[101][101];

int findfri(int x) {

while(x != fri[x])

x = fri[x];

return x;

}

void Union(int a, int b) {

int fria = findfri(a);

int frib = findfri(b);

if(fria != frib)

fri[fria] = frib;

}

int main() {

int n, m, k, a, b, c;

scanf("%d %d %d", &n, &m, &k);

fri.resize(n + 1);

for(int i = 1; i <= n; i++)

fri[i] = i;

for(int i = 0; i < m; i++) {

scanf("%d %d %d", &a, &b, &c);

if(c == 1)

Union(a, b);

else {

enemy[a][b] = 1;

enemy[b][a] = 1;

}

for(int i = 0; i < k; i++) {

scanf("%d %d", &a, &b);

if(findfri(a) == findfri(b) && enemy[a][b] == 0)

printf("No problem\n");

else if(findfri(a) != findfri(b) && enemy[a][b] == 0)

printf("OK\n");

else if(findfri(a) == findfri(b) && enemy[a][b] == 1)

printf("OK but...\n");

else if(enemy[a][b] == 1)

printf("No way\n");

}

return 0;

}

L3-003. 社交集群-PAT团体程序设计天梯赛GPLT（并查集）

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。
输入格式：
输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：
Ki: hi[1] hi[2] … hi[Ki]
其中Ki（>0）是第i个人的兴趣的数量，hi[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。
输出格式：
首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
输出样例：
3
4 3 1
分析：并查集。先写好init、findFather、Union。
0. 每个社交圈的结点号是人的编号，而不是课程。课程是用来判断是否处在一个社交圈的。
1. course[t]表示任意一个喜欢t活动的人的编号。如果当前的课程t，之前并没有人喜欢过，那么就course[t] = i，i为它自己的编号，表示i为喜欢course[t]的一个人的编号
2. course[t]是喜欢t活动的人的编号，那么findFather(course[t])就是喜欢这个活动的人所处的社交圈子的根结点，合并根结点和当前人的编号的结点i。即Union(i, findFather(course[t]))，把它们处在同一个社交圈子里面
3. isRoot[i]表示编号i的人是不是它自己社交圈子的根结点，如果等于0表示不是根结点，如果不等于0，每次标记isRoot[findFather(i)]++，那么isRoot保存的就是如果当前是根结点，那么这个社交圈里面的总人数
4. isRoot中不为0的编号的个数cnt就是社交圈圈子的个数
5. 把isRoot从大到小排列，输出前cnt个，就是社交圈人数的从大到小的输出顺序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> father, isRoot;
int cmp1(int a, int b){
    return a > b;
}
int findFather(int x) {
    int a = x;
    while(x != father[x])
        x = father[x];
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB)
        father[faA] = faB;
}
int main() {
    int n, k, t, cnt = 0;
    int course[1001] = {0};
    scanf("%d", &n);
    father.resize(n + 1);
    isRoot.resize(n + 1);
    for(int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &t);
            if(course[t] == 0)
                course[t] = i;
            Union(i, findFather(course[t]));
        }
    }
    for(int i = 1; i <= n; i++)
        isRoot[findFather(i)]++;
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0)
            cnt++;
    }
    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> father, isRoot;

int cmp1(int a, int b){

return a > b;

}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != father[a]) {

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB)

father[faA] = faB;

}

int main() {

int n, k, t, cnt = 0;

int course[1001] = {0};

scanf("%d", &n);

father.resize(n + 1);

isRoot.resize(n + 1);

for(int i = 1; i <= n; i++)

father[i] = i;

for(int i = 1; i <= n; i++) {

scanf("%d:", &k);

for(int j = 0; j < k; j++) {

scanf("%d", &t);

if(course[t] == 0)

course[t] = i;

Union(i, findFather(course[t]));

}

for(int i = 1; i <= n; i++)

isRoot[findFather(i)]++;

for(int i = 1; i <= n; i++) {

if(isRoot[i] != 0)

cnt++;

}

printf("%d\n", cnt);

sort(isRoot.begin(), isRoot.end(), cmp1);

for(int i = 0; i < cnt; i++) {

printf("%d", isRoot[i]);

if(i != cnt - 1) printf(" ");

}

return 0;

}

1107. Social Clusters (30)-PAT甲级真题（并查集）

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].
Output Specification:
For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
Sample Output:
3
4 3 1

题目大意：有n个人，每个人喜欢k个活动，如果两个人有任意一个活动相同，就称为他们处于同一个社交网络。求这n个人一共形成了多少个社交网络。
分析：并查集。先写好init、findFather、Union。
0. 每个社交圈的结点号是人的编号，而不是课程。课程是用来判断是否处在一个社交圈的。
1. course[t]表示任意一个喜欢t活动的人的编号。如果当前的课程t，之前并没有人喜欢过，那么就course[t] = i，i为它自己的编号，表示i为喜欢course[t]的一个人的编号
2. course[t]是喜欢t活动的人的编号，那么findFather(course[t])就是喜欢这个活动的人所处的社交圈子的根结点，合并根结点和当前人的编号的结点i。即Union(i, findFather(course[t]))，把它们处在同一个社交圈子里面
3. isRoot[i]表示编号i的人是不是它自己社交圈子的根结点，如果等于0表示不是根结点，如果不等于0，每次标记isRoot[findFather(i)]++，那么isRoot保存的就是如果当前是根结点，那么这个社交圈里面的总人数
4. isRoot中不为0的编号的个数cnt就是社交圈圈子的个数
5. 把isRoot从大到小排列，输出前cnt个，就是社交圈人数的从大到小的输出顺序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> father, isRoot;
int cmp1(int a, int b){return a > b;}
int findFather(int x) {
    int a = x;
    while(x != father[x])
        x = father[x];
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) father[faA] = faB;
}
int main() {
    int n, k, t, cnt = 0;
    int course[1001] = {0};
    scanf("%d", &n);
    father.resize(n + 1);
    isRoot.resize(n + 1);
    for(int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &t);
            if(course[t] == 0)
                course[t] = i;
            Union(i, findFather(course[t]));
        }
    }
    for(int i = 1; i <= n; i++)
        isRoot[findFather(i)]++;
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0) cnt++;
    }
    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> father, isRoot;

int cmp1(int a, int b){return a > b;}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != father[a]) {

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB) father[faA] = faB;

}

int main() {

int n, k, t, cnt = 0;

int course[1001] = {0};

scanf("%d", &n);

father.resize(n + 1);

isRoot.resize(n + 1);

for(int i = 1; i <= n; i++)

father[i] = i;

for(int i = 1; i <= n; i++) {

scanf("%d:", &k);

for(int j = 0; j < k; j++) {

scanf("%d", &t);

if(course[t] == 0)

course[t] = i;

Union(i, findFather(course[t]));

}

for(int i = 1; i <= n; i++)

isRoot[findFather(i)]++;

for(int i = 1; i <= n; i++) {

if(isRoot[i] != 0) cnt++;

}

printf("%d\n", cnt);

sort(isRoot.begin(), isRoot.end(), cmp1);

for(int i = 0; i < cnt; i++) {

printf("%d", isRoot[i]);

if(i != cnt - 1) printf(" ");

}

return 0;

}

1025. PAT Ranking (25)-PAT甲级真题

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (<=100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (<=300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

题目大意：有n个考场，每个考场有若干数量的学生，给出每个考场中考生的编号和分数，要求算排名，输出所有考生的编号、排名、考场号、考场内排名
分析：先按照考场内排名然后赋值给总数组fin，然后总排名，最后输出。注意相同的分数情况下按照学号的从小到大排列，但是他们的排名应该是一样的数字～

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct student {
    long long int no;
    int score, finrank, loca, locarank;
};
bool cmp1(student a, student b) {
    return a.score != b.score ? a.score > b.score : a.no < b.no;
}
int main() {
    int n, m;
    scanf("%d", &n);
    vector<student> fin;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &m);
        vector<student> v(m);
        for(int j = 0; j < m; j++) {
            scanf("%lld %d", &v[j].no, &v[j].score);
            v[j].loca = i;
        }
        sort(v.begin(), v.end(), cmp1);
        v[0].locarank = 1;
        fin.push_back(v[0]);
        for(int j = 1; j < m; j++) {
            v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);
            fin.push_back(v[j]);
        }
    }
    sort(fin.begin(), fin.end(), cmp1);
    fin[0].finrank = 1;
    for(int j = 1; j < fin.size(); j++)
        fin[j].finrank = (fin[j].score == fin[j - 1].score) ? (fin[j - 1].finrank) : (j + 1);
    printf("%d\n", fin.size());
    for(int i = 0; i < fin.size(); i++)
        printf("%013lld %d %d %d\n", fin[i].no, fin[i].finrank, fin[i].loca, fin[i].locarank);
    return 0;
}

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

struct student {

long long int no;

int score, finrank, loca, locarank;

};

bool cmp1(student a, student b) {

return a.score != b.score ? a.score > b.score : a.no < b.no;

}

int main() {

int n, m;

scanf("%d", &n);

vector<student> fin;

for(int i = 1; i <= n; i++) {

scanf("%d", &m);

vector<student> v(m);

for(int j = 0; j < m; j++) {

scanf("%lld %d", &v[j].no, &v[j].score);

v[j].loca = i;

}

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

v[0].locarank = 1;

fin.push_back(v[0]);

for(int j = 1; j < m; j++) {

v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);

fin.push_back(v[j]);

}

sort(fin.begin(), fin.end(), cmp1);

fin[0].finrank = 1;

for(int j = 1; j < fin.size(); j++)

fin[j].finrank = (fin[j].score == fin[j - 1].score) ? (fin[j - 1].finrank) : (j + 1);

printf("%d\n", fin.size());

for(int i = 0; i < fin.size(); i++)

printf("%013lld %d %d %d\n", fin[i].no, fin[i].finrank, fin[i].loca, fin[i].locarank);

return 0;

}

1066. Root of AVL Tree (25)-PAT甲级真题（AVL树）

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print ythe root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88

题目大意：AVL树是自平衡二叉搜索树。在AVL树中，任何节点的两个子子树的高度最多相差一个；如果在任何时候它们相差多于一个，则重新平衡以恢复此属性。图1-4说明了旋转规则～现在给出一系列插入，要求输出根节点的值～

分析：写出建AVL（平衡二叉搜索树）的代码模版即可，rotateLeft表示左旋，rotateRight表示右旋，rotateLeftRight表示先左旋后右旋，rotateRightLeft表示先右旋后左旋，getHeight表示获取传入结点的子树的高度，insert表示插入建树的过程，如果root为空，直接新建结点插入即可～如果当前要插入的值小于root->val，则插入root的左子树；如果当前要插入的值大于root->val，则插入root的右子树～如果插入后左右子树高度差大于1，再根据值的大小比较进行旋转调整使树平衡～插入完成后返回root指针赋值给main函数里的root～最后输出root的val值～

#include <iostream>
using namespace std;
struct node {
    int val;
    struct node *left, *right;
};
node *rotateLeft(node *root) {
    node *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}
node *rotateRight(node *root) {
    node *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}
node *rotateLeftRight(node *root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
node *rotateRightLeft(node *root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
int getHeight(node *root) {
    if(root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node *insert(node *root, int val) {
    if(root == NULL) {
        root = new node();
        root->val = val;
        root->left = root->right = NULL;
    } else if(val < root->val) {
        root->left = insert(root->left, val);
        if(getHeight(root->left) - getHeight(root->right) == 2)
            root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
    } else {
        root->right = insert(root->right, val);
        if(getHeight(root->left) - getHeight(root->right) == -2)
            root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
    }
    return root;
}
int main() {
    int n, val;
    scanf("%d", &n);
    node *root = NULL;
    for(int i = 0; i < n; i++) {
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d", root->val);
    return 0;
}

#include <iostream>

using namespace std;

struct node {

int val;

struct node *left, *right;

};

node *rotateLeft(node *root) {

node *t = root->right;

root->right = t->left;

t->left = root;

return t;

}

node *rotateRight(node *root) {

node *t = root->left;

root->left = t->right;

t->right = root;

return t;

}

node *rotateLeftRight(node *root) {

root->left = rotateLeft(root->left);

return rotateRight(root);

}

node *rotateRightLeft(node *root) {

root->right = rotateRight(root->right);

return rotateLeft(root);

}

int getHeight(node *root) {

if(root == NULL) return 0;

return max(getHeight(root->left), getHeight(root->right)) + 1;

}

node *insert(node *root, int val) {

if(root == NULL) {

root = new node();

root->val = val;

root->left = root->right = NULL;

} else if(val < root->val) {

root->left = insert(root->left, val);

if(getHeight(root->left) - getHeight(root->right) == 2)

root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);

} else {

root->right = insert(root->right, val);

if(getHeight(root->left) - getHeight(root->right) == -2)

root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);

}

return root;

}

int main() {

int n, val;

scanf("%d", &n);

node *root = NULL;

for(int i = 0; i < n; i++) {

scanf("%d", &val);

root = insert(root, val);

}

printf("%d", root->val);

return 0;

}