题目描述

$N$ 是一个正奇数。我们称一个长度为 $N$ 的序列 $S$ 是 M 型序列，当前仅当对于所有的 $i=2,4,6,\dots,N-1$（即偶数位），都有 $S_{i-1}<S_{i}$ 且 $S_{i}>S_{i+1}$。

现在给定你一个长度为 $N$ 的序列 $A$，请你判断能否通过将 $A$ 序列里的元素打乱位置使其变为一个 M 型序列。

输入格式

输入共两行

第一行一个整数 $N$，表示序列长度。

第二行共 $N(1\le N\le2\times10^5)$个整数，第 $i$ 个整数为 $A_{i}(1\le A_{i}\le10^9)$。

输出格式

共一行一个字符串，如果 $A$ 序列能够通过被打乱元素顺序变成 M 型序列，输出 Yes，否则输出 No。

样例 1

输入

5
1 2 3 4 5

输出

Yes

样例 2

输入

5
1 6 1 6 1

输出

Yes

样例 3

输入

5
1 6 6 6 1

输出

No