結果
問題 | No.2053 12345... |
ユーザー | tatananonano |
提出日時 | 2022-12-18 04:24:15 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 30,013 bytes |
コンパイル時間 | 7,235 ms |
コンパイル使用メモリ | 296,644 KB |
実行使用メモリ | 9,296 KB |
最終ジャッジ日時 | 2024-11-17 13:12:23 |
合計ジャッジ時間 | 8,552 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | WA | - |
testcase_03 | AC | 20 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 3 ms
5,248 KB |
testcase_23 | AC | 10 ms
5,248 KB |
testcase_24 | AC | 23 ms
5,248 KB |
testcase_25 | AC | 75 ms
6,956 KB |
testcase_26 | AC | 36 ms
5,340 KB |
testcase_27 | AC | 22 ms
5,248 KB |
testcase_28 | AC | 19 ms
5,248 KB |
testcase_29 | AC | 50 ms
5,464 KB |
testcase_30 | AC | 20 ms
5,248 KB |
testcase_31 | AC | 47 ms
5,420 KB |
testcase_32 | AC | 84 ms
7,144 KB |
ソースコード
#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <deque>#include <list>#include <unordered_map>#include <unordered_set>#include <iomanip>#include <set>#include <map>#include <ctime>#include <stack>#include <functional>#include <cstdio>#include <string>#include <iostream>#include <limits>#include <stdexcept>#include <numeric>#include <fstream>#include <atcoder/all>#include <chrono>#include <utility>#include <cassert>#include <random>#include <stdio.h>#include <stdlib.h>using namespace std;using namespace atcoder;using namespace internal;typedef long long ll;typedef long double LD;typedef double D;typedef pair<ll,ll> P;typedef map<ll,ll> M;#define rep(i,n) for(ll i=0;i<n;i++)#define rrep(i,n) for(ll i=1;i<n;i++)#define jep(i, a, n)for (ll i =(ll)a; i<(ll)n;++i)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define fore(i,a) for(const auto &i:a)#define all(x) (x).begin(),(x).end()#define frac(x) x-floor(x)#define eb emplace_back#define pb push_back#define lb lower_bound#define ub upper_bound#define SUM(x) accumulate(all(x),0)#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())#define TFU(s) transform(all(s),begin(s),::toupper);//大文字にする#define TFL(s) transform(all(s),begin(s),::tolower);//小文字にする#define replace(s,a,A) replace(s,'a','A')//str(s)のaをAにする#define NP(a) next_permutation(all(a))#define grid_check(a,b,h,w) (a<0 or b<0 or a>=h or b>=w)#define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする#define PQ priority_queue#define PQD PQ<P,vector<P>,greater<P>>//小さい順に吐く#define PQS PQ<ll,vec,greater<ll>>//大きい順に吐く#define fi first#define se second#define bit(n,k) ((n>>k)&1)#define cl clock()/CLOCKS_PER_SEC#define printd(n,x) cout<<fixed<<setprecision(n)<<x<<endl#define cinv(a,n); rep(i,n){cin>>a[i];}#define cinvv(a,n,m); rep(i,n){rep(j,m){cin>>a[i][j];}}#define popcount(n) __builtin_popcountll(n)template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;}template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;}typedef vector<ll> vec;typedef vector<vec> mat;const LD PI=acos(-1);//const ll mod = 1000000009;//手動で切り替える.const ll mod = 998244353;//const ll mod = 1000000007;using mint =modint998244353;//using mint =modint1000000009;//using mint =modint1000000007;const ll INF = (1LL<<(60));ll dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};ll modpow(ll a,ll n,ll mod){if(mod==1)return 0;ll ret=1;ll p=a%mod;while(n){if(n&1)ret=ret*p%mod;p=p*p%mod;n>>=1;}return ret; }M factor(ll n) {M ret;for(ll i=2;i*i<=n;i++){while(n%i==0){ret[i]++;n /= i;}}if(n != 1){ret[n]=1;}return ret;}//素因数分解vec divisor(ll n){vec K;for(ll i=1;i*i<=n;i++){if(n%i==0){K.pb(i);if(i*i!=n)K.pb(n/i);}}sort(all(K));return K;}//約数列挙ll modlog(ll a,ll b,ll p){ll g=1;for(ll i=p;i;i/=2)(g*=a)%=p;g=gcd(g,p);ll t=1,c=0;for(;t%g;c++){if(t==b)return c;(t*=a)%=p;}if(b%g){return -1;}t/=g;b /= g;ll n=p/g,h=0,gs=1;for(;h*h<n; h++){(gs*=a)%=n;}unordered_map<ll,ll>bs;for(ll s=0,e=b;s<h;bs[e]=++s){(e *= a) %= n;}for(ll s = 0, e = t; s< n;){(e*=gs)%=n;s+=h;if(bs.count(e))return c+s-bs[e];}return -1;}//a^x≡b(modp) x_min //task : x=0が効かないから別の用意するbool isprime(ll N){if(N==1){return false;}if(N==2){return true;}for(ll i=2;i*i<=N;i++){if(N%i==0)return false;}return true;}//Naiveな素数判定static inline ll my_div(ll n, ll p) { return double(n) / p; };ll prime_counting(ll N) {ll N2 = sqrt(N);ll NdN2 = my_div(N, N2);vec hl(NdN2);rrep(i,NdN2){hl[i] = my_div(N, i) - 1;}vec hs(N2 + 1);iota(begin(hs),end(hs), -1);for (int x = 2, pi = 0; x <= N2; ++x) {if (hs[x] == hs[x - 1]) {continue;}ll x2 = ll(x) * x;ll imax = min<ll>(NdN2, my_div(N, x2) +1);ll ix = x;for (ll i = 1; i < imax; ++i) {hl[i] -= (ix < NdN2 ? hl[ix] : hs[my_div(N, ix)]) - pi;ix += x;}for (int n = N2; n >= x2; n--) {hs[n]-= hs[my_div(n, x)] - pi;}++pi;}return hl[1];}mat binomial(ll n) {mat a(n+1,vec(n+1));rep(i,n+1)rep(j,i+1){if(j==0||j==i)a[i][j]=1;else a[i][j]=a[i-1][j-1]+a[i-1][j];}return a;}//O(n^2)template<typename T>T phi(T n) {T ret=n;for(T i = 2; i * i <= n; i++){if(n % i == 0){ret -= ret / i;while(n % i == 0) n /= i;}}if(n > 1){ret -= ret /n;}return ret;}template<typename T>T extgcd(T a, T b, T &x, T &y){T d = a;if(b != 0){d=extgcd(b,a%b,y,x);y -= (a / b) * x;}else {x = 1;y = 0;}return d;}mat mat_mul(mat&a,mat&b){mat res(a.size(),vec(b[0].size()));rep(i,a.size()){rep(j,b[0].size()){rep(k,b.size()){(res[i][j]+=a[i][k]*b[k][j])%=mod;}}}return res;}mat matpow(mat a,ll n){mat res(a.size(),vec(a.size()));rep(i,a.size())res[i][i]=1;while(n>0){if(n & 1)res=mat_mul(a,res);a=mat_mul(a,a);n>>=1;}returnres;}//#define mant vector<vector<mint>>//なにこれ//mant mant_mul(mant&a,mant&b){mant res(a.size(),vector<mint>(b[0].size()));rep(i,a.size()){rep(j,b[0].size()){rep(k,b.size()){(res[i][j]+=a[i][k]*b[k][j])}}}return res;}//mant mantpow(mant a,ll n){mant res(a.size(),vector<mint>(a.size()));rep(i,a.size())res[i][i]=1;while(n>0){if(n & 1)res=mant_mul(a,res);a=mant_mul(a,a);n>>=1;}return res;}vec base(ll x,ll b){//(b)進数の配列を用意vec ret;ll t = 1, k = abs(b);while(x) {ret.emplace_back((x * t) % k);if(ret.back() < 0){ret.back() += k;}x -= ret.back() * t;x /= k;t *= b / k;}if(ret.empty()) {ret.emplace_back(0);}reverse(begin(ret), end(ret));return ret;}vec slide_min(const vec &v,ll k){deque<ll> q;vec ret;rep(i,v.size()){while(!q.empty() and v[q.back()]>=v[i])q.pop_back();q.push_back(i);if(i-k+1>=0){ret.pb(v[q.front()]);if(q.front()==i-k+1){q.pop_front();}}}return ret;}struct SuccinctIndexableDictionary {size_t length;size_t blocks;vector< unsigned > bit, sum;SuccinctIndexableDictionary() = default;SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {bit.assign(blocks, 0U);sum.assign(blocks, 0U);}void set(ll k) {bit[k >> 5] |= 1U << (k & 31);}void build() {sum[0] = 0U;for(ll i = 1; i < blocks; i++) {sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);}}bool operator[](ll k) {return (bool((bit[k >> 5] >> (k & 31)) & 1));}ll rank(ll k) {return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));}ll rank(bool val, ll k) {return (val ? rank(k) : k - rank(k));}};template< typename T, ll MAXLOG >struct WaveletMatrix {size_t length;SuccinctIndexableDictionary matrix[MAXLOG];ll mid[MAXLOG];WaveletMatrix() = default;WaveletMatrix(vector< T > v): length(v.size()) {vector< T > l(length), r(length);for(ll level = MAXLOG - 1; level >= 0; level--) {matrix[level] = SuccinctIndexableDictionary(length + 1);ll left = 0, right = 0;for(ll i = 0; i <length; i++) {if(((v[i] >> level) & 1)) {matrix[level].set(i);r[right++] = v[i];} else {l[left++] = v[i];}}mid[level] = left;matrix[level].build();v.swap(l);for(ll i = 0; i < right; i++) {v[left + i] = r[i];}}}pair< ll, ll > succ(bool f, ll l, ll r, lllevel) {return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};}T access(ll k) {T ret = 0;for(ll level = MAXLOG - 1; level >= 0; level--) {bool f = matrix[level][k];if(f) ret |= T(1) << level;k = matrix[level].rank(f, k) + mid[level] * f;}return ret;}T operator[](const ll &k) {return access(k);}ll rank(const T &x, ll r) {ll l = 0;for(ll level = MAXLOG - 1; level >= 0; level--) {tie(l, r) = succ((x>> level) & 1, l, r, level);}return r - l;}T kth_smallest(ll l, ll r, ll k) {assert(0 <= k && k < r - l);T ret = 0;for(ll level = MAXLOG - 1; level >= 0; level--) {ll cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);bool f = cnt <= k;if(f) {ret |=T(1) << level;k -= cnt;}tie(l, r) = succ(f, l, r, level);}return ret;}T kth_largest(ll l, ll r, ll k) {return kth_smallest(l, r, r - l - k - 1);}ll range_freq(ll l, ll r, T upper) {ll ret = 0;for(ll level = MAXLOG - 1; level >= 0; level--) {bool f = ((upper >> level) & 1);if(f) {ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);}tie(l, r) = succ(f, l, r, level);}returnret;}ll range_freq(ll l, ll r, T lower, T upper) {return range_freq(l, r, upper) - range_freq(l, r, lower);}T prev_value(ll l, ll r, T upper) {ll cnt = range_freq(l, r, upper);return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);}T next_value(ll l, ll r, T lower) {ll cnt = range_freq(l, r, lower);return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);}};template< typename T, ll MAXLOG >struct CWM {WaveletMatrix< ll, MAXLOG > mat;vector< T > ys;CWM(const vector< T > &v) : ys(v) {sort(begin(ys), end(ys));ys.erase(unique(begin(ys), end(ys)), end(ys));vec t(v.size());for(ll i = 0; i < v.size();i++) t[i] = get(v[i]);mat = WaveletMatrix< ll, MAXLOG >(t);}inline ll get(const T& x) {return lower_bound(begin(ys), end(ys), x) - begin(ys);}T access(ll k) {return ys[mat.access(k)];}T operator[](const ll &k) {return access(k);}ll rank(const T &x, ll r) {auto pos = get(x);if(pos == ys.size() || ys[pos] != x) {return 0;}return mat.rank(pos, r);}T kth_smallest(ll l, ll r, ll k) {return ys[mat.kth_smallest(l, r, k)];}T kth_largest(ll l, ll r, ll k) {return ys[mat.kth_largest(l, r, k)];}ll range_freq(ll l, ll r, T upper) {return mat.range_freq(l, r, get(upper));}ll range_freq(ll l, ll r, T lower, T upper) {return mat.range_freq(l, r, get(lower), get(upper));}T prev_value(ll l, ll r, T upper) {auto ret = mat.prev_value(l, r, get(upper));return ret == -1 ? T(-1) : ys[ret];}T next_value(ll l, ll r, T lower) {auto ret = mat.next_value(l, r, get(lower));return ret == -1 ? T(-1) : ys[ret];}};namespace inner {using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;template <typename T>T gcd(T a, T b) {while (b) swap(a %= b, b);return a;}template <typename T>T inv(T a, T p) {T b = p, x = 1, y = 0;while (a) {T q = b / a;swap(a, b %= a);swap(x, y -= q * x);}assert(b == 1);return y < 0 ? y + p : y;}template <typename T, typename U>T modpow(T a, U n, T p) {T ret = 1 % p;for (; n; n >>= 1, a = U(a) * a % p)if (n & 1) ret = U(ret) * a % p;return ret;}} // namespace innernamespace my_rand {// [0, 2^64 - 1)uint64_t rng() {static uint64_t x_ =uint64_t(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) *10150724397891781847ULL;x_ ^= x_ << 7;return x_ ^= x_ >> 9;}// [l, r)int64_t randint(int64_t l, int64_t r) {assert(l < r);return l + rng() % (r - l);}// choose n numbers from [l, r) without overlappingvector<int64_t> randset(int64_t l, int64_t r, int64_t n) {assert(l <= r && n <= r - l);unordered_set<int64_t> s;for (int64_t i = n; i; --i) {int64_t m = randint(l, r + 1 - i);if (s.find(m) != s.end()) m = r - i;s.insert(m);}vector<int64_t> ret;for (auto& x : s) ret.push_back(x);return ret;}// [0.0, 1.0)double rnd() {union raw_cast {double t;uint64_t u;};constexpr uint64_t p = uint64_t(1023 - 64) << 52;return rng() * ((raw_cast*)(&p))->t;}template <typename T>void randshf(vector<T>& v) {int n = v.size();for (int loop = 0; loop < 2; loop++)for (int i = 0; i < n; i++) swap(v[i], v[randint(0, n)]);}} // namespace my_randusing my_rand::randint;using my_rand::randset;using my_rand::randshf;using my_rand::rnd;using my_rand::rng;struct ArbitraryLazyMontgomeryModInt {using mint = ArbitraryLazyMontgomeryModInt;using i32 = int32_t;using u32 = uint32_t;using u64 = uint64_t;static u32 mod;static u32 r;static u32 n2;static u32 get_r() {u32 ret = mod;for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;return ret;}static void set_mod(u32 m) {assert(m < (1 << 30));assert((m & 1) == 1);mod = m;n2 = -u64(m) % m;r = get_r();assert(r * mod == 1);}u32 a;ArbitraryLazyMontgomeryModInt() : a(0) {}ArbitraryLazyMontgomeryModInt(const int64_t &b): a(reduce(u64(b % mod + mod) * n2)){};static u32 reduce(const u64 &b) {return (b + u64(u32(b) * u32(-r)) * mod) >> 32;}mint &operator+=(const mint &b) {if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}mint &operator-=(const mint &b) {if (i32(a -= b.a) < 0) a += 2 * mod;return *this;}mint &operator*=(const mint &b) {a = reduce(u64(a) * b.a);return *this;}mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}mint operator+(const mint &b) const { return mint(*this) += b; }mint operator-(const mint &b) const { return mint(*this) -= b; }mint operator*(const mint &b) const { return mint(*this) *= b; }mint operator/(const mint &b) const { return mint(*this) /= b; }bool operator==(const mint &b) const {return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);}bool operator!=(const mint &b) const {return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);}mint operator-() const { return mint() - mint(*this); }mint pow(u64 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const mint &b) {return os << b.get();}friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = ArbitraryLazyMontgomeryModInt(t);return (is);}mint inverse() const { return pow(mod - 2); }u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static u32 get_mod() { return mod; }};typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::mod;typename ArbitraryLazyMontgomeryModInt::u32ArbitraryLazyMontgomeryModInt::r;typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::n2;struct montgomery64 {using mint = montgomery64;using i64 = int64_t;using u64 = uint64_t;using u128 = __uint128_t;static u64 mod;static u64 r;static u64 n2;static u64 get_r() {u64 ret = mod;for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;return ret;}static void set_mod(u64 m) {assert(m < (1LL << 62));assert((m & 1) == 1);mod = m;n2 = -u128(m) % m;r = get_r();assert(r * mod == 1);}u64 a;montgomery64() : a(0) {}montgomery64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};static u64 reduce(const u128 &b) {return (b + u128(u64(b) * u64(-r)) * mod) >> 64;}mint &operator+=(const mint &b) {if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}mint &operator-=(const mint &b) {if (i64(a -= b.a) < 0) a += 2 * mod;return *this;}mint &operator*=(const mint &b) {a = reduce(u128(a) * b.a);return *this;}mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}mint operator+(const mint &b) const { return mint(*this) += b; }mint operator-(const mint &b) const { return mint(*this) -= b; }mint operator*(const mint &b) const { return mint(*this) *= b; }mint operator/(const mint &b) const { return mint(*this) /= b; }bool operator==(const mint &b) const {return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);}bool operator!=(const mint &b) const {return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);}mint operator-() const { return mint() - mint(*this); }mint pow(u128 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const mint &b) {return os << b.get();}friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = montgomery64(t);return (is);}mint inverse() const { return pow(mod - 2); }u64 get() const {u64 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static u64 get_mod() { return mod; }};typename montgomery64::u64 montgomery64::mod, montgomery64::r, montgomery64::n2;namespace fast_factorize {using u64 = uint64_t;template <typename mint>bool miller_rabin(u64 n, vector<u64> as) {if (mint::get_mod() != n) mint::set_mod(n);u64 d = n - 1;while (~d & 1) d >>= 1;mint e{1}, rev{int64_t(n - 1)};for (u64 a : as) {if (n <= a) break;u64 t = d;mint y = mint(a).pow(t);while (t != n - 1 && y != e && y != rev) {y *= y;t *= 2;}if (y != rev && t % 2 == 0) return false;}return true;}bool is_prime(u64 n) {if (~n & 1) return n == 2;if (n <= 1) return false;if (n < (1LL << 30))return miller_rabin<ArbitraryLazyMontgomeryModInt>(n, {2, 7, 61});elsereturn miller_rabin<montgomery64>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});}template <typename mint, typename T>T pollard_rho(T n) {if (~n & 1) return 2;if (is_prime(n)) return n;if (mint::get_mod() != n) mint::set_mod(n);mint R, one = 1;auto f = [&](mint x) { return x * x + R; };auto rnd_ = [&]() { return rng() % (n - 2) + 2; };while (1) {mint x, y, ys, q = one;R = rnd_(), y = rnd_();T g = 1;constexpr int m = 128;for (int r = 1; g == 1; r <<= 1) {x = y;for (int i = 0; i < r; ++i) y = f(y);for (int k = 0; g == 1 && k < r; k += m) {ys = y;for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y));g = inner::gcd<T>(q.get(), n);}}if (g == n) dog = inner::gcd<T>((x - (ys = f(ys))).get(), n);while (g == 1);if (g != n) return g;}exit(1);}using i64 = long long;vector<i64> inner_factorize(u64 n) {if (n <= 1) return {};u64 p;if (n <= (1LL << 30))p = pollard_rho<ArbitraryLazyMontgomeryModInt, uint32_t>(n);elsep = pollard_rho<montgomery64, uint64_t>(n);if (p == n) return {i64(p)};auto l = inner_factorize(p);auto r = inner_factorize(n / p);copy(begin(r), end(r), back_inserter(l));return l;}vector<i64> factorize(u64 n) {auto ret = inner_factorize(n);sort(begin(ret), end(ret));return ret;}map<i64, i64> factor_count(u64 n) {map<i64, i64> mp;for (auto &x : factorize(n)) mp[x]++;return mp;}vector<i64> divisors(u64 n) {if (n == 0) return {};vector<pair<i64, i64>> v;for (auto &p : factorize(n)) {if (v.empty() || v.back().first != p) {v.emplace_back(p, 1);} else {v.back().second++;}}vector<i64> ret;auto f = [&](auto rc, int i, i64 x) -> void {if (i == (int)v.size()) {ret.push_back(x);return;}for (int j = v[i].second;; --j) {rc(rc, i + 1, x);if (j == 0) break;x *= v[i].first;}};f(f, 0, 1);sort(begin(ret), end(ret));return ret;}} // namespace fast_factorizeusing fast_factorize::divisors;using fast_factorize::factor_count;using fast_factorize::factorize;using fast_factorize::is_prime;using namespace fast_factorize;struct Barrett {using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;u32 m;u64 im;Barrett() : m(), im() {}Barrett(int n) : m(n), im(u64(-1) / m + 1) {}constexpr inline i64 quo(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;return m <= r ? x - 1 : x;}constexpr inline i64 rem(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;return m <= r ? r + m : r;}constexpr inline pair<i64, int> quorem(u64 n) {u64 x = u64((__uint128_t(n) * im) >> 64);u32 r = n - x * m;if (m <= r) return {x - 1, r + m};return {x, r};}constexpr inline i64 pow(u64 n, i64 p) {u32 a = rem(n), r = m == 1 ? 0 : 1;while (p) {if (p & 1) r = rem(u64(r) * a);a = rem(u64(a) * a);p >>= 1;}return r;}};struct prime_power_binomial {int p, q, M;vector<int> fac, ifac, inv;int delta;Barrett bm, bp;prime_power_binomial(int _p, int _q) : p(_p), q(_q) {assert(1 < p && p <= ((1LL << 30) - 1));assert(_q > 0);long long m = 1;while (_q--) {m *= p;assert(m <=((1LL << 30) - 1));}M = m;bm = Barrett(M), bp = Barrett(p);enumerate();delta = (p == 2 && q >= 3) ? 1 : M - 1;}void enumerate() {int MX = min<int>(M, 20000000 + 10);fac.resize(MX);ifac.resize(MX);inv.resize(MX);fac[0] = ifac[0] = inv[0] = 1;fac[1] = ifac[1] = inv[1] = 1;for (int i = 2; i < MX; i++) {if (i % p == 0) {fac[i] = fac[i - 1];fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1));i++;} else {fac[i] = bm.rem(1LL * fac[i - 1] * i);}}ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1);for (int i = MX - 2; i > 1; --i) {if (i % p == 0) {ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));ifac[i - 1] = ifac[i];i--;} else {ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));}}}long long Lucas(long long n, long long m) {int res = 1;while (n) {int n0, m0;tie(n, n0) = bp.quorem(n);tie(m, m0) = bp.quorem(m);if (n0 < m0) return 0;res = bm.rem(1LL * res * fac[n0]);int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]);res = bm.rem(1LL * res * buf);}return res;}long long C(long long n, long long m) {if (n < m || n < 0 || m < 0) return 0;if (q == 1) return Lucas(n, m);long long r = n - m;int e0 = 0, eq = 0, i = 0;int res = 1;while (n) {res = bm.rem(1LL * res * fac[bm.rem(n)]);res = bm.rem(1LL * res * ifac[bm.rem(m)]);res = bm.rem(1LL * res * ifac[bm.rem(r)]);n = bp.quo(n);m = bp.quo(m);r = bp.quo(r);int eps = n - m - r;e0 += eps;if (e0 >= q) return 0;if (++i >= q) eq += eps;}if (eq & 1) res = bm.rem(1LL * res * delta);res = bm.rem(1LL * res * bm.pow(p, e0));return res;}};struct binomial_mod {int mod;vector<int> M;vector<prime_power_binomial> cs;binomial_mod(long long md) : mod(md) {assert(1 <= md);assert(md <= ((1LL << 30) - 1));for (int i = 2; i * i <= md; i++) {if (md % i == 0) {int j = 0, k = 1;while (md % i == 0) md /= i, j++, k *= i;M.push_back(k);cs.emplace_back(i, j);assert(M.back() == cs.back().M);}}if (md != 1) {M.push_back(md);cs.emplace_back(md, 1);}assert(M.size() == cs.size());}long long binom(long long n, long long m) {if (mod == 1) return 0;vector<long long> rem, d;for (int i = 0; i < (int)cs.size(); i++) {rem.push_back(cs[i].C(n, m));d.push_back(M[i]);}return atcoder::crt(rem, d).first;}};#define is_prime(x) is_prime_constexpr(x)//FPS!!ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }ll modsqrt(ll a,ll mod){if(mod==2||a==0) return a;if(modPow(a,(mod-1)/2,mod)!=1) return -1;if(mod%4==3) return modPow(a,(mod+1)/4,mod);ll q=mod-1;ll s=0;while(q%2==0){q/=2;s++;}ll z=1;random_device rnd;while(modPow(z=rnd()%mod,(mod-1)/2,mod)!=mod-1);ll c=modPow(z,q,mod),t=modPow(a,q,mod),r=modPow(a,(q+1)/2,mod),m=s;while(m>1){if(modPow(t,1<<(m-2),mod)==1){c*=c;c%=mod;m--;}else{tie(c,t,r,m)=make_tuple(c*c%mod,c*c%mod*t%mod,c*r%mod,m-1);}}return r%mod;}template<class T>struct FormalPowerSeries:vector<T>{using vector<T>::vector;using vector<T>::operator=;using F = FormalPowerSeries;F operator-() const{F res(*this);for(auto &e:res) e=-e;return res;}F &operator*=(const T &g){for(auto &e:*this) e*=g;return *this;}F &operator/=(const T &g){assert(g!=T(0));*this*=g.inv();return *this;}F &operator+=(const F &g){int n=(*this).size(),m=g.size();for(int i=0;i<min(n,m);i++){(*this)[i]+=g[i];}return *this;}F &operator-=(const F &g){int n=(*this).size(),m=g.size();for(int i=0;i<min(n,m);i++){(*this)[i]-=g[i];}return *this;}F &operator<<=(const int d) {int n=(*this).size();(*this).insert((*this).begin(),d,0);(*this).resize(n);return *this;}F &operator>>=(const int d) {int n=(*this).size();(*this).erase((*this).begin(),(*this).begin()+min(n, d));(*this).resize(n);return *this;}F inv(int d=-1) const{int n=(*this).size();assert(n!=0&&(*this)[0]!=0);if(d==-1) d=n;assert(d>0);F res{(*this)[0].inv()};while(res.size()<d){int m=size(res);F f(begin(*this),begin(*this)+min(n,2*m));F r(res);f.resize(2*m);r.resize(2*m);vector<T> s=convolution(f,r);s.resize(2*m);for(int i=0;i<2*m;i++){s[i]=-s[i];}s[0]+=2;vector<T> g=convolution(s,r);g.resize(2*m);res=g;}res.resize(n);return res;}F &operator*=(const F &g){int n=(*this).size();*this=convolution(*this,g);(*this).resize(n);return (*this);}F &operator/=(const F &g){int n=(*this).size();*this=convolution(*this,g.inv());(*this).resize(n);return (*this);}void onemultiply(const int d,const T c){int n=(*this).size();for(int i=n-d-1;i>=0;i--){(*this)[i+d]+=(*this)[i]*c;}}void onediv(const int d,const T c){int n=(*this).size();for(int i=n-d-1;i>=0;i--){(*this)[i+d]-=(*this)[i]*c;}}T eval(const T &a) const {T x(1),res(0);for(auto e:*this) res+=e*x,x*=a;return res;}F differential() const {int n=(*this).size();F res(n);for(int i=0;i<n-1;i++){res[i]=T(i+1)*(*this)[i+1];}res[n-1]=0;return res;}F Integral() const {int n=(*this).size();F res(n);for(int i=1;i<n;i++){res[i]=(*this)[i-1]/T(i);}res[0]=0;return res;}F log() const{assert((*this)[0]==1);int n=(*this).size();F u=(*this).differential();F d=(*this);u/=d;u=u.Integral();u.resize(n);return u;}F exp(ll d=-1) const{ll n=(*this).size();assert(n!=0&&(*this)[0]==0);if(d==-1) d=n;assert(d>0);F res{1};while(res.size()<d){ll m=size(res);F f(begin(*this),begin(*this)+min(n,2*m));F r(res);f.resize(2*m);r.resize(2*m);r=r.log();f-=r;f[0]++;F g=f*res;g.resize(2*m);res=g;}res.resize(n);return res;}F pow(ll a){ll n=(*this).size();F res(n);for(ll i=0;i<n;i++){res[i]=(*this)[i];}if(a==0){F s(n);if(n>0){s[0]=T(1);}for(ll i=0;i<n;i++){res[i]=s[i];}return res;}int l=0;while(l<n&&res[l]==0) l++;if(l>(n-1)/a||l==n){F s(n);for(ll i=0;i<n;i++){res[i]=s[i];}return res;}T t=res[l];res.erase(res.begin(),res.begin()+l);res/=t;F g=res.log();for(ll i=0;i<n;i++){res[i]=g[i];}res*=a;g=res.exp();for(ll i=0;i<n;i++){res[i]=g[i];}res*=t.pow(a);res.insert(res.begin(),l*a,0);return res;}F sqrt(int k=-1){int n=(*this).size();if(k==-1){k=n;}ll m=T::mod();if((*this)[0]==T(0)){for(int i=1;i<int((*this).size());i++){if((*this)[i]!=T(0)){if(i&1) return {};if(n-i/2<=0)break;auto ret=(*this>>i).sqrt(n-i/2)<<(i/2);if(int(ret.size())<n) return {};return ret;}}F g(n);for(int i=0;i<n;i++){g[i]=0;}return g;}else{if(modsqrt((*this)[0].val(),m)==-1){return {};}F ret{T(modsqrt((*this)[0].val(),m))};for(int i=1;i<n;i<<=1){ret.resize(2*i);ret=(ret+(*this)/ret);ret/=T(2);}return ret;}}pair<F,F> division(F g){F f=(*this);int n=f.size();int m=g.size();if(n<m){F p(0);return {p,f};}F p(n-m+1),q(n-m+1);for(int i=0;i<n-m+1;i++) p[i]=f[n-i-1];for(int i=0;i<n-m+1&&i<m;i++) q[i]=g[m-i-1];p/=q;for(int i=0;i<(n-m+1)/2;i++) swap(p[i],p[(n-m+1)-i-1]);g.resize(n);g*=p;for(int i=0;i<n;i++) f[i]-=g[i];int v=n-m+1,u=0;for(int i=0;i<n;i++) if(f[i].val()) chmax(u,i+1);p.resize(v);f.resize(u);return {p,f};}F operator*(const T &g) const { return F(*this)*=g;}F operator-(const T &g) const { return F(*this)-=g;}F operator*(const F &g) const { return F(*this)*=g;}F operator-(const F &g) const { return F(*this)-=g;}F operator+(const F &g) const { return F(*this)+=g;}F operator/(const F &g) const { return F(*this)/=g;}F operator<<(const int d) const { return F(*this)<<=d;}F operator>>(const int d) const { return F(*this)>>=d;}};using fps = FormalPowerSeries<mint>;fps partition(ll N) {fps po(N + 1);po[0] = 1;rrep(k,N+1){if(1LL * k * (3 * k + 1) / 2 <= N) po[k * (3 * k + 1) / 2] += (k % 2 ? -1 : 1);if(1LL * k * (3 * k - 1) / 2 <= N) po[k * (3 * k - 1) / 2] += (k % 2 ? -1 : 1);}return po.inv();}int main(){ll n;cin>>n;vec a(n);cinv(a,n);ll ans=0;vec res;ll cnt=1;rep(i,n-1){if((a[i]-a[i+1])==1){cnt++;}else{res.pb(cnt);cnt=0;}}res.pb(cnt);cnt=1;rep(i,n-1){if((a[i]-a[i+1])==-1){cnt++;}else{res.pb(cnt);cnt=0;}}res.pb(cnt);for(auto e:res){if(e==1){}else{ans+=e*(e-1)/2;}}cout<<ans<<endl;}