#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
// siz[i]  以  i 为根节点的树的大小
int l[N], r[N], siz[N], v[N], tot = 1;

// 往 根为 u 的子树中插入 x
void insert(int u, int x) {
	siz[u]++;   // 记录子树的节点个数
	if (v[u] == 0) {
		v[u] = x;
		return ;
	}
	if (x < v[u]) {
		if (l[u] == 0)
			l[u] = ++tot;
		insert(l[u], x);
	} else {
		if (r[u] == 0)
			r[u] = ++tot;
		insert(r[u], x);
	}
}

int  query(int u, int x) {
	int lc = 1;  // u 本身这个
	if (l[u])
		lc += siz[l[u]];
	if (lc == x)
		return v[u];
	if (x < lc)
		return query(l[u], x);
	else
		return query(r[u], x - lc);
}

// 二叉搜索树：
// 左子树小于根节点， 右子树大于根节点
// 中序遍历：递增
// 快速查找某个值 时间复杂度 深度
// 完全二叉树：O(logn)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
// 根节点的下标为 1
int l[N], r[N], v[N], tot = 1;

// 当前树根节点是u，插入 x
void insert(int u, int x) {
	if (v[u] == 0) {  // 根节点没有值，直接放
		v[u] = x;
		return ;
	}
	// 判断放左子树还是右子树
	if (v[u] > x) {
		if (l[u] == 0) {
			l[u] = ++tot;
		}
		insert(l[u], x);
	}
	if (v[u] < x) {
		if (r[u] == 0) {
			r[u] = ++tot;
		}
		insert(r[u], x);
	}
}

void query(int u, int x) {
	if (v[u] == x) {
		cout << endl;
		return ;
	}
	if (x < v[u]) {
		cout << "E";
		query(l[u], x);
	} else {
		cout << "W";
		query(r[u], x);
	}
}


int main() {
	return 0;
}

// 根据中序遍历和后序遍历建树
int l[N], r[N];
int maxdep;

void dfs(int u, int dep) {
	maxdep = max(maxdep, dep);
	if (l[dep] == 0)
		l[dep] = v[u];
	r[dep] = v[u];
	if (lson[u])
		dfs(lson[u], dep + 1);
	if (rson[u])
		dfs(rson[u], dep + 1);
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;
int pre[N], in[N], mp[N];
int lson[N], rson[N];
int n;
bool flg = 1 ;


int build(int l1, int r1, int  l2, int r2) {
	if (l1 > r1)
		return 0;
	// 找到当前树 的根节点
	int u = pre[l1];
	// 判断根节点是否在 l2, r2 之间
	int id = mp[u];  // 根节点的位置
	if (id < l2 || id > r2) {
		flg = 0;  // 标记是否凑出树
		return 0;
	}
	// l1 的位置根，
	//  l2 , id
	lson[u] = build(l1 + 1, l1 + (id - l2), l2, id - 1);
	rson[u] = build(l1 + (id - l2) + 1, r1, id + 1, r2);
	return u;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> pre[i];
	for (int i = 1; i <= n; i++) {
		cin >> in[i];
		mp[in[i]] = i;
	}
	// 以 1 为根节点
	if (pre[1] != 1) {
		cout << -1;
		return 0;
	}
	build(1, n, 1, n);
	if (flg == 0) {
		cout << -1;
		return 0;
	}
	for (int i = 1; i <= n; i++)
		cout << lson[i] << " " << rson[i] << endl;
}

#include <bits/stdc++.h>
using namespace std;
map<int, long long > mp;

void build(int h) {
	int t;
	cin >> t;
	if (t == -1)
		return;
	mp[h] += t;
	build(h - 1);
	build(h + 1);
}

int main() {
	build(0);
	for (auto t : mp)
		cout << t.second << " ";
	return 0;
}

E

#include <bits/stdc++.h>
using namespace std;
const int N  = 30;
char pre[N], in[N];

// l1 - r1, 先序遍历
// l2 -  r2 中序遍历
void solve(int l1, int r1, int l2, int r2) {
	if (l1 > r1)
		return ;
	// 根一定是 l1
	int mid;
	for (int i = l2; i <= r2; i++) {
		if (in[i] == pre[l1])
			mid = i;
	}
	// 左子树有几个 ， mid  - l2
	solve(l1 + 1, l1 + (mid - l2 ), l2, mid - 1);
	// 右子树
	solve(l1 + (mid - l2) + 1,  r1, mid + 1, r2);
	cout << pre[l1];
}

int main() {
	cin >> in + 1 >> pre + 1;
	int len = strlen(in + 1);
	solve(1, len, 1, len);
	return 0;
}

#D

//数组存储：
//根节点： i
//左子树： 2 * i
//右子树： 2 * i + 1
//
//链式存储
//value[N]  存储值
//lson[N]  存储 左子树的编号
//rson[N]  存储 右子树的编号
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N];
int n;

// 根左右
void pre(int u) {
	cout << u << " ";
	if (l[u])
		pre(l[u]);
	if (r[u])
		pre(r[u]);
}

// 左根右
void in(int u) {
	
	if (l[u])
		pre(l[u]);
	cout << u << " ";
	if (r[u])
		pre(r[u]);
}

// 左右根
void post(int u) {
	if (l[u])
		pre(l[u]);
	if (r[u])
		pre(r[u]);
	cout << u << " ";
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
	}
	return 0;
}

for (auto  c : s) {
	if (c == 'U') {
		if (top && stk[top] == 'L' || stk[top] == 'R')
			top--;
		else
			stk[++top] = 'U';
	} else {
		stk[++top] = c;
	}
}

for(int i=1;i<=top ;i++){
	== u .  x/=2;
	== L  x = x*2;
	==R ,  x = x*2+1
}

#B

#include <bits/stdc++.h>
using namespace std;
int n, a[1 << 17], id[1 << 17];

int main() {
	cin >> n;
	for (int i = 1; i <= (1 << n); i++) {
		cin >> a[i];
		id[(1 << n) + i - 1] = i;  // 放在叶子节点
	}
	for (int i = (1 << n) - 1 ; i >= 2; i--) {
		if (a[id[2 * i]] > a[id[2 * i + 1]])
			id[i] = id[2 * i];
		else
			id[i] = id[2 * i + 1];
	}
	if (a[id[2]] > a[id[3]])
		cout << id[3];
	else
		cout << id[2];
	return 0;
}