作者：cup-pyy
链接：https://zhuanlan.zhihu.com/p/720725545
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 2);
        a[0] = a[n + 1] = 2e9;
        for(int i = 1; i <= n; i++) cin >> a[i];
        LL ans = 0;
        {
            vector<int> stk{0};
            for(int i = 1; i <= n; i++){
                while(!stk.empty() and a[stk.back()] < a[i]){
                    stk.pop_back();
                }
                ans += i - stk.back() - 1;
                stk.push_back(i);
            }
        }
        {
            vector<int> stk{n + 1};
            for(int i = n; i >= 1; i--){
                while(!stk.empty() and a[stk.back()] < a[i]) stk.pop_back();
                if (a[stk.back()] != a[i]) ans += stk.back() - i - 1;
                stk.push_back(i);
            }
        }
        cout << ans << '\n';
    }

}

answer.code:4:1: error: extended character 。 is not valid in an identifier
    4 | 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
      | ^
answer.code:4:1: error: extended character 。 is not valid in an identifier
answer.code:1:1: error: ‘作者：cup’ does not name a type
    1 | 作者：cup-pyy
      | ^~~~~~~~~
In file included from /usr/include/c++/13/iosfwd:42,
                 from /usr/include/c++/13/ios:40,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:6:
/usr/include/c++/13/bits/postypes.h:68:11: error: ‘ptrdiff_t’ does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/13/bits/postypes.h:41:1: note: ‘ptrdiff_t’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/13/bits/exception_ptr.h:38,
                 from /usr/include/c++/13/exception:164,
                 from /usr/include/c++/13/ios:41:
/usr/include/c++/13/new:126:26: error: declaration of ‘operator new’ as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:126:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/13/cwchar:44,
                 from /usr/include/c++/13/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:128:26: error: declaration of ‘operator new []’ as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:128:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:135:34: error: ‘std::size_t’ has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                  ^~~~~~
/usr/include/c++/13/new:137:36: error: ‘std::size_t’ has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                    ^~~~~~
/usr/include/c++/13/new:140:26: error: declaration of ‘operator new’ as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:140:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:140:52: error: expected primary-expression before ‘const’
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/13/new:142:26: error: declaration of ‘operator new []’ as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:142:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:142:54: error: expected primary-expression before ‘const’
  142 | _GLIBCXX_N...