// dfs
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// const int N = 100010, M = 100010;
// int n, m;
// struct Node
// {
// int id;
// Node* next;
// Node(int _id): id(_id), next(NULL) {}
// }*head[N]; //每个点都用一个单链表来存(临街表)
// bool st[N]; //判重数组,每个点只能走一次
// void add(int a, int b) //头插法
// {
// auto p = new Node(b); // 创建一个新的点
// p -> next = head[a]; //
// head[a] = p;
// }
// void dfs(int u)
// {
// st[u] = true;
// printf("%d ", u);
// for (auto p = head[u]; p; p = p -> next)
// {
// int j = p -> id;
// if (!st[j]) dfs(j); //能搜直接搜
// }
// // printf(">%d<", u); // 回溯时的输出顺序。即逆序
// }
// int main()
// {
// scanf("%d%d", &n, &m);
// while(m --)
// {
// int a, b;
// scanf("%d%d", &a, &b);
// add(a, b); //添加一条a到b的边
// }
// // 图不一定连通,故要枚举所有点
// for (int i = 1; i <= n; i ++)
// if(!st[i]) //如果没被搜过 搜之
// dfs(i);
// return 0;
// }
// bfs. 用队列
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <queue>
// using namespace std;
// const int N = 100010, M = 100010;
// int n, m;
// struct Node
// {
// int id;
// Node* next;
// Node(int _id) : id(_id), next(NULL){}
// }*head[N];
// bool st[N];
// void add(int a, int b) //头插法
// {
// auto p = new Node(b); // 创建一个新的点
// p -> next = head[a]; //
// head[a] = p;
// }
// void bfs()
// {
// queue<int> q;
// q.push(1);
// st[1] = true;
// while (q.size())
// {
// auto t = q.front();
// q.pop();
// printf("%d ", t);
// for (auto p = head[t]; p; p = p -> next)
// {
// int j = p -> id;
// if(!st[j])
// {
// st[j] = true;
// q.push(j);
// }
// }
// }
// }
// int main()
// {
// scanf("%d%d", &n, &m);
// while(m --)
// {
// int a, b;
// scanf("%d%d", &a, &b);
// add(a, b); //添加一条a到b的边
// }
// bfs();
// return 0;
// }
// 2018年 408大题
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// int n;
// int find(int q[], int n)
// {
// bool h[n + 1];
// for (int i = 0; i <= n; i ++ )
// if(q[i] >= 1 && q[i] <= n)
// h[q[i]] = true;
// for (int i = 1; i <= n; i ++ )
// if(!h[i]) return i;
// return n + 1;
// }
// int main()
// {
// cin >> n;
// int q[n];
// for (int i = 0; i <= n; i ++)
// cin >> q[i];
// cout << find(q, n) << ' ';
// }
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// const int N = 10010;
// int n;
// int q[N];
// 二分查找 王道模拟题1
// 参考题解https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
//只能与右边界进行比较
//二分目的是判断m在哪个排序数组中,从而缩小区间 在q[mid] > q[l]时无法判断mid在哪个排序数组中。本质上是由于r初始值肯定在右排序数组中
//l初始值无法确定在哪个排序数组中
// int main()
// {
// cin >> n;
// for (int i = 0; i < n; i ++) cin >> q[i];
// int l = 0, r = n - 1;
// while(l < r)
// {
// int mid = (l + r) / 2;
// if (q[mid] < q[r]) r = mid;
// else if (q[mid] > q[r]) l = mid + 1;
// else r --; //去重
// }
// cout << q[r];
// return 0;
// }
// 王道模拟题2
// 可采用归并排序
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// const int N = 10010;
// int n, m;
// int q[N], w[N];
// int main()
// {
// cin >> m >> n;
// for (int i = 1; i <= n + m; i ++) cin >> q[i];
// int k = 1, i = 1, j = m + 1;
// while (i <= m && j <= n + m)
// {
// if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
// else w[k ++ ] = q[j ++];
// }
// while (i <= m) w[k ++ ] = q[i ++ ];
// while (j <= n + m) w[k ++ ] = q[j ++ ];
// for (int i = 1; i <= n + m; i ++ ) cout << w[i] << ' ';
// return 0;
// }
// 王道模拟题3
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// struct Node
// {
// char val;
// Node *next;
// Node(char _val) : val(_val), next(NULL){}
// };
// int n;
// char j;
// bool symmetry(Node* head)
// {
// if (!head) return false;
// // 对链表的后半部分进行反转
// int mid = n / 2;
// auto a = head;
// Node* b = NULL;
// for (int i = 0; i < mid - 1; i ++ ) a = a -> next;
// if(n % 2 == 1) b = a -> next -> next;
// else b = a -> next;
// Node* c = NULL;
// a -> next = NULL;
// while (b)
// {
// auto d = b -> next;
// b -> next = c;
// c = b;
// b = d;
// }
// while (head)
// {
// if (head -> val == c -> val)
// {
// head = head -> next;
// c = c ->next;
// }else break;
// }
// if (head) return false;
// return true;
// }
// int main()
// {
// Node* head = new Node(0);
// Node* q = head;
// cin >> n;
// while (n --)
// {
// cin >> j;
// auto p = new Node(j);
// q -> next = p;
// q = p;
// }
// head = head -> next;
// if(symmetry(head)) puts("yes");
// else puts("no");
// }
// 王道4
// https://blog.csdn.net/weixin_44713619/article/details/109231600
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <stack>
// using namespace std;
// struct TreeNode
// {
// char val;
// TreeNode *left;
// TreeNode *right;
// TreeNode(char x) : val(x), left(NULL), right(NULL) {}
// };
// const int N = 100010;
// char x;
// stack<char> s;
// void create_tree(TreeNode* &root)
// {
// char c;
// cin >> c;
// if (c == '#') root = NULL;
// else
// {
// root = new TreeNode(c);
// create_tree(root -> left);
// create_tree(root -> right);
// }
// }
// bool path(TreeNode* root, char x)
// {
// if (!root) return false;
// s.push(root -> val);
// if(root -> val == x) return true;
// bool flag = false;
// if (root -> left) flag = path(root -> left, x);
// //当左子树没有查到时,去查找右子树
// if (!flag && root -> right) flag = path(root -> right, x);
// if(!flag) s.pop();
// return flag;
// }
// void inorder(TreeNode* root)
// {
// if (!root) return;
// inorder(root -> left);
// cout << root -> val << ' ';
// inorder(root -> right);
// }
// int main()
// {
// cin >> x;
// TreeNode* root = new TreeNode('#');
// // 二叉树的建立
// create_tree(root);
// // 中序遍历
// inorder(root);
// puts(" ");
// // 找到指定节点到根节点的路径;
// path(root, x);
// while (!s.empty())
// {
// char b = s.top();
// cout << b << ' ';
// s.pop();
// }
// cout << s.size();
// return 0;
// }
/* 王道5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int cnt = 0;
int q[N], st[N];
// void get_sub() //暴力做法
// {
// for (int i = 0; i < n - 1; i ++ )
// {
// int t = q[i] -q[i + 1];
// for (int j = i + 1; j < n; j ++ )
// {
// if (t < q[i] - q[j]) t = q[i] - q[j];
// }
// st[i] = t;
// }
// for (int i = 0; i < n - 1; i ++ ) cout << st[i] << ' ';
// }
int get_sub1(int l, int r, int &max, int &min) //分治法 分别找到左边的最大最小值,右边最大最小值,进行比较
{
cnt ++;
printf("-----%d------\n", cnt);
printf("此次执行g:%d %d max=%d min=%d\n", l, r, max, min);
if (l == r)
{
max = min = q[l];
return 0;
}
int mid = (l + r) >> 1;
printf("mid=%d\n", mid);
//如果得到最大差值的两个数都在左边
int leftmax = 0, leftmin = 0, rightmax = 0, rightmin = 0;
int diff_left = get_sub1(l, mid, leftmax, leftmin);
printf("gleft(%d %d)=%d leftmax=%d leftmin=%d\n", l, mid, diff_left, leftmax, leftmin);
int diff_right = get_sub1(mid + 1, r, rightmax, rightmin);
printf("gright(%d %d)=%d rightmax=%d rightmin=%d\n", mid + 1, r, diff_right, rightmax, rightmin);
max = (leftmax > rightmax) ? leftmax : rightmax;
min = (leftmin < rightmin) ? leftmin : rightmin;
printf("g(%d %d) max=%d min=%d\n", l, r, max, min);
int cross_diff = leftmax - rightmin;
printf("左右差值=%d\n", cross_diff);
int max_diff = (diff_left > diff_right) ? diff_left : diff_right;
max_diff = (max_diff > cross_diff) ? max_diff : cross_diff;
printf("maxdiff= %d\n", max_diff);
printf("-----%d------\n", cnt);
return max_diff;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];
// get_sub();
int M = 0, m = 0;
get_sub1(0, n - 1, M, m);
return 0;
}
*/
//王道6
/*
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int q[N], b[N];
void build(int l, int r) //暴力做法
{ int k = 1;
for (int i = 1; i <= n; k ++, i += 2) b[k] = q[i];
for (int j = 2; j <= n; k ++, j += 2 ) b[k] = q[j];
for (int i = 1; i <= n; i ++ ) cout << b[i] << ' ';
}
void build1()
{
int cnt = 1;
int i = (n % 2 == 0) ? n - 1 : n;
while (i > 1)
{
int tmp = q[i - 1];
for (int j = 0; j < cnt; j ++ )// 将奇数块往前平移
{
q[i + j - 1] = q[i + j];
}
q[i - 1 + cnt] = tmp; //将偶数值移到奇数快后面
i -= 2;
cnt ++;
}
for (int i = 1; i <= n; i ++ ) printf("序号为%d 现值%d\n", i, q[i]);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
for (int i = 1; i <= n; i ++ ) printf("序号为%d 原值%d\n", i, q[i]);
puts("------");
// build(1, n);
build1();
}
*/
// 王道7
/*
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int q[N], s[N]; // s[N]为前缀和数组
int result()
{
int res = 0;
for (int i = 1; i <= n; i ++)
{
for (int j = i; j <= n; j ++ )
{
int tmp = s[j] - s[i - 1];
if (tmp > res) res = tmp;
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> s[i];
// for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + s[i]; //这题可以不用申请一个新的数组,可以用原数组作为前缀和数组
// for (int i = 1; i <= n; i ++ ) cout << s[i] << ' ';
// int min = result();
// printf("子数组之和的最大值为%d\n", min);
//剑指 Offer 42. 连续子数组的最大和。做法2 时间复杂度o[n]
for (int i = 1; i <= n; i ++ )
{
if(s[i - 1] <= 0) s[i] = s[i]; // 是对前缀和做法的一个优化,如果前面数组值非正数,对整个子数组的值没有提升效果,故不加进来
else s[i] = s[i - 1] + s[i];
}
for (int i = 1; i <= n; i ++) cout << s[i] << ' ';
return 0;
}
*/
// 王道8
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// struct Node
// {
// int val;
// Node *left;
// Node *right;
// Node(int val) : val(val), left(NULL), right(NULL){}
// };
// const int N = 10010;
// int q[N];
// void create_tree(Node* &root) //前序遍历的顺序
// {
// int c;
// cin >> c;
// if (c == 0) root = NULL;
// else
// {
// root = new Node(c);
// create_tree(root -> left);
// create_tree(root -> right);
// }
// }
// void inorder(Node* root)
// {
// if (!root) return;
// inorder(root -> left);
// cout << root -> val << ' ';
// inorder(root -> right);
// }
// int find(Node* root, int height)
// {
// printf("height=%d\n", height);
// if (!root) return 0;
// if(!root -> left && !root -> right)
// {
// q[height] ++;
// return height;
// }
// find(root -> left, height + 1);
// find(root -> right, height + 1);
// }
// int main()
// {
// Node* root = new Node(0);
// create_tree(root);
// inorder(root);
// int n = find(root, 1);
// puts(" ");
// cout << n << ' ';
// puts(" ");
// for (int i = 1; i <= n; i ++) cout << q[i] << ' ';
// return 0;
// }
//天勤1
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// using namespace std;
// const int N = 10010;
// int n;
// char q[N];
// void MinDis(int l, int r)
// {
// if (l >= r) return;
// int res = 0;
// for (int i = 0; i < n; i ++)
// { int j = r;
// while (i < j)
// {
// if (q[i] == q[j])
// {
// int tmp = j - i;
// res = (res > tmp) ? res : tmp;
// break;
// }
// j --;
// }
// }
// cout << res << " ";
// }
// int main()
// {
// cin >> n;
// for (int i = 0; i < n; i ++ ) cin >> q[i];
// MinDis(0, n - 1);
// return 0;
// }
//天勤2. 错版
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <stack>
// using namespace std;
// const int N = 10010;
// struct TreeNode
// {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode(int val) : val(val), left(NULL), right(NULL){}
// };
// int n;
// int q[N];
// stack<int> s;
// void create_tree(TreeNode* &root) //前序遍历的顺序建立二叉树
// {
// int c;
// cin >> c;
// if (c == 0) root = NULL;
// else
// {
// root = new TreeNode(c);
// create_tree(root -> left);
// create_tree(root -> right);
// }
// }
// void postorder(TreeNode* root)
// {
// if(!root) return;
// postorder(root -> left);
// postorder(root -> right);
// s.push(root -> val);
// }
// bool judge(stack<int> s, int q[])
// {
// while (!s.empty())
// {
// for (int i = n - 1; i >= 0; i --)
// {
// if(s.top() != q[i]) return false;
// else s.pop();
// }
// }
// return true;
// }
// int main()
// {
// cin >> n;
// for (int i = 0; i < n; i ++ ) cin >> q[i];
// TreeNode* root = new TreeNode(0);
// create_tree(root);
// postorder(root);
// cout << judge(s, q);
// return 0;
// }
// 天勤2。正版
// 剑指 Offer 33. 二叉搜索树的后序遍历序列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int q[N];
int n;
bool isseq(int l, int r)
{
if (l >= r) return true;
int root = q[r];
int i = l;
while(q[i] < root) i ++; //找到左子树的根
int j = i;
while(q[i] > root) i ++;
return i == r && isseq(l, j - 1) && isseq(j, r - 1);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];
cout << isseq(0, n - 1);
return 0;
}