Language: C++

#include <bits/stdc++.h>
#include <math.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int n;
    cin >> n;
    vector<pair<ll, ll>> b(n); // i-A.at(i), A.at(i)
    for (ll i = 0; i < n; i++) {
        ll a;
        cin >> a;
        b.push_back(make_pair(i - a, a));
    }

    sort(b.begin(), b.end());
    ll ans = 0;
    ll mx = -1;
    ll mi = n;
    for (ll i = 0; i < n; i++) {
        if (i >= mi && i <= mx)
            continue;
        ll a = b.at(i).second;
        auto it_u = upper_bound(b.begin() + i, b.end(), make_pair(i + a, INF_64));
        auto it_l = lower_bound(b.begin() + i, b.end(), make_pair(i + a, -INF_64));
        mx = max((ll)(it_u - b.begin()), mx);
        mi = min((ll)(it_l - b.begin()), mi);
        ans += distance(it_l, it_u);
    }

    cout << ans << endl;
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = const std::pair<long long int, long int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >]':
/usr/include/c++/14/bits/stl_algo.h:1993:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, long int>; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
 1993 |           if (__comp(__val, __middle))
      |               ~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:2028:32:   required from '_FIter std::upper_bound(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Tp = pair<long long int, long int>]'
 2028 |       return std::__upper_bound(__first, __last, __val,
      |              ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
 2029 |                                 __gnu_cxx::__ops::__val_less_iter());
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:35:32:   required from here
   35 |         auto it_u = upper_bound(b.begin() + i, b.end(), make_pair(i + a, INF_64));
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:98:22: error: no match for 'operator<' (operand types are 'const std::pair<long long int, long int>' and 'std::pair<long long int, long long int>')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:181:
/usr/include/c++/14/bits/regex.h:1143:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const sub_match<_BiIter>&)'
 1143 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1143:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)'
 1224 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1224:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1317 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1317:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)'
 1391 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1391:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1485 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1485:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)'
 1560 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1560:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1660 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/regex.h:1660:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   deduced conflicting types for parameter '_T2' ('long int' and 'long long int')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'const std::pair<long long int, long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_itera