描述

给你一个下标从 $0$ 开始的整数数组 nums ，你必须将数组划分为一个或多个 $连续$ 子数组。

如果获得的这些子数组中每个都能满足下述条件$之一$ ，则可以称其为数组的一种 $有效$ 划分：

1. 子数组 $恰$ 由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组 $恰$ 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组 $恰$ 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

​如果数组 $至少$ 存在一种有效划分，返回 1 ，否则，返回 0 。

格式

输入

第一行输入一个整数 $n$ ，$(2 <= n <=10^5)$ 第二行输入长度为 $n$ 的数组 $a$$(1 <= a_i <=10^6 )$ 。

输出

输出是否存在有效划分。

样例

5
4 4 4 5 6

1