// https://codeforces.com/problemset/problem/452/F

// 一個1到n的排列，請判斷該排列內(nèi)部是否存在一個3個元素的子序列(可以不連續(xù))，使得這個子序列是等差序列。n<=3e5

?

// a1,x,a2 是等差數(shù)列，則 a1,a2 關于x對稱。

// 所以出現(xiàn)在x之前的數(shù)據(jù)關于x對稱，則不存在3個數(shù)的等差數(shù)列以x為中間項；如果出現(xiàn)在x之前的數(shù)據(jù)關于x不對稱，則存在3個數(shù)的等差數(shù)列。

// 例如：1，5，3，2，4，出現(xiàn)在3之前的數(shù)據(jù)1，5關于3對稱，則不存在3個數(shù)的等差數(shù)列1，3，5以3為中間項；

// 1，3，2，4，5，出現(xiàn)在3之前的數(shù)據(jù)1關于3不對稱，則存在3個數(shù)的等差數(shù)列1，3，5。

// 思路類似于下題

// https://codeforces.com/contest/213/problem/E

//? 線段樹+hash

// 首先我們可以知道A序列是1~n的排列，那么我們可以先在B序列中把1~n的排列找出來，看其相對位置是否與A相同(hash可做)，相同即表明存在一個d=0滿足條件。

// 以此類推，我們接下來可以把B中 2~ n + 1的排列找出來，如果其每位-1后相對順序還是與A序列一致，即存在d=1也滿足。。。

// 線段樹中保存一個長度為n的序列的hash。

// hash函數(shù)值：? a[1]*23^(n-1) + a[2]*23^(n-2) + a[3]*23^(n-3)+? ......? ?

?

// 另一個線段樹例子：CF競賽題目講解_CF213E(線段樹+hash)

// https://www.bilibili.com/video/BV1KB4y1Q79G?spm_id_from=333.999.0.0