Problem:


Score: 500 points

Problem Statement

Given is a permutation P of \{1, 2, \ldots, N\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Sample Input 1

3
2 3 1

Sample Output 1

5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAIVrdF0C/+19fXxT1f3/TdKW8NQELazyIEGqFJHSQoHWxxQauIEUkAKyKYY0SWk1TbrmBouiVts6Y6iiP+f8urmxzW1uc9Pt6xT9OiiCFBUUH3hQfEAHckNB0ClWHeT3+Zxzbnruzb0VnL/vH7/XovTk8z6f8/D5nM/5nId7c86tLs8ss8kkKB+zcLmA1A9HOAntZHiLP80CWJnQH/6OFkYKOUBnc3xOwakKe1jWSmhlfBb4lwX/ysyULjM7VeFIxqeEJi7MFviPUxX+6ypBFQqCI50O67p3GUX3LluuCq1ZFLf3U6czs3Q9LF0P41dCwSyoQkW+LPZvEcMXMbmUsJLxVXL8+FlwUArgd3EhpcWFTlW4mvGt1qS7EtLlCKf/sbNwISvPSC+FrP5KqLTDpFB9zbTSSaHAxFB9ONY8sbls2sRppUXRSNFkUic74509b7FKj/msznnMBjC+8JrOlpOPTH/4pq8OXh74sPjx43WzVmJcGUuHTdIettdljelvNgmlQgtkjXGXsFb/6ztTdg24ba33Yf/fX7i7IbXtznb/sDer17Wu+b7zk4mfeK/NdawsLnTt8nQevqAz78FBM38+snH9Kvf1T/WlnwNQgbN08DfM+vgkkz7+V0Eft6ctTP0ZbYC/mq2fz80G+MsG5XYY8Is5+ng/A3y+Af6jLH283qDcCwzyKTPQ898M8HMM8plioM8VBvn4DPL51IB/tJF+DMr9Pwbtkm1gP4sMyn3WgH+wQX2WG/CfMLDzMQb8vzVo32cM8GcN8r/FQA/1BnqbYiDXKgP95Bnw/9lArgaDelYY5HPEoP7lBvm8Z6AfyQB/yaCeHxv0o3EGenjdIP9XDOp5sYG8fzcodyzkM0YYLqytoeNFPsPPYvhO/3LVeDMum+L7Gb6U4QOzGO6jeAvDf8PKXX6OU1XubKYfx3A1PhfKHQL5dAaWc6O4INyYRfH9DFfGsbdMtNzlNWp+m6JPTbkLsmk+LTXqfC5j+Xcy3M4iZjO5nAGNXEz/T2jqL8C4GpUC/gkTcCydJni9KxoiYW9U8jVJXq/gnbPSuzC4oj4qBZtmhnzRaDAqeN2LqryBYBODF1XNDEXCwUW+mlCQxunHeBuluqagL+C9PrjK64dvEoL+Zp+3tikY9Aab/cFGqT4SFrw/mFcdLYViG0uKvVhSVGqKrHItnFvtc/tdJDpSDhH14WiwSXKHXK6F1ZFFXoyYWy1N9UurGoPAWDIFeG6oDwTDwFkvuVYCQ7VUMt3rhXpEbvDWQFV8oVDEv5KmjJZMqa0PB7y19U1RyRupdS2Y629ooMVNrQ3FonVKFtP4LPy+qERygIgpTbGwVN8AwjQ1RZoqS7gEERAi6GtQKu0HtMRf52vySk2+eikK9QUpIIcaX7Ter3C7F3kXFXtd1dO8C+ZWT/GGmL5I4STnctByQ30YVEmrEJ1ZgnqKknovWgQZlvdmWB9ewbLVKZ3olipXKquPREG2aLDUDYpjYgA+DZTlCwV7AY3ArPB0TUCBfKMh1KBCJFY7KE9XI1P9oaCvyQUxk71uqBP8k4jZgOiTi5VWiMSwubxNvvCKIBSptOY00ppgs5I3HFE3KEZP5xpbE7/IDTXj7REBjaysKWrA1MNgA5K/jrNbqFu1N9jQKK2CvtAInSnS5FsRdDELLZlKpaZNUhOrNW6PKcCDyvauaG72NgabopGwL1QP2a4sZgpMV7NyMmuVKCiryguKu94LOQYUdJqvsTEYDhAhAQmEFqyEppDKQXaiRQnlXHJGtSPtUOoH/WemBTMzSIvJwjc0kMTTWemc7spBddQ7uBoaVMaSNksqKtE/6cDAq3EfkSmNMcnlZ1Z6Zn0ArBRbmxjcfFBZQyQQJPLNA3cEhTb7aupXlqD5Reu9fvSJXvQ40LNrIy7eeZWAJKx/hpjQGRoH5ulNQXAJK0Fcvd43k3W2uXxbl95Q55O0Dcu6HjYsOvUG6s/h2wo/tAhSJYJ3cfgGNPuFwWisIYiRfspWG4E8BFCNFAkJtcFIrVC7IihFEQlBBFO2FGyul4SGYIO/oZEEjauEWn8oEg0KDaQlgBHzZMNHg68+LKBzF2bPnOmdUlQszPa4Z8z0Ti4qKU1/nVw0VZi5dGnFDLe3pGgKhZcuBe7SopISFVnOU3SNh/9ZBOV7FvzLJv+ZyTf6V2Dfs9Mp8LuFfcsh/wTGkcN4c1hsPxZaOe7M/3LIuGwS9mf3rrMWXLBqIK4ka3OUdaxZOMnii+Hf/fc+kIOr93AOxWLD6/tjLVal+bPIWK/MY954/PpsXNG2M35fz0/MuLJdy+j4rePNuML9BaOl8fdZUd4/sfx6vHQ+kKPZz1DmP9lsfZuev9f04vyMoYXDZ3D4Wg4v4/BODp/J4co8DfFyvj4cfjG/6xLoxSv5/Dn8cj4fDr+Cw/OXU7wfN5ci8zAON3N4IYdbOLyYw7P4dSSH83p2cng/fh3M4VZ+3sfh/Tl8KYcP4NuLwwdyeB2HD+LwRg4fzOHNHJ7LtzuH2zj8Tg638/bA4UM4/EEO5+f36zj8bA5/lMMrOPwJDh/K4es5fBhvJxz+PQ7fxuH5vH1y+HAO38vhl/L2xuEjOFzm8JEcfpzDR3F4D4efq9oo6MVHc7CVw/l1rJ3Dx/D2z+Hn8fbP4WN5++fwAt7+Ofx83v45/DLe/jl8HG//HF7I2z+Hj+ftn8Mv5O2fwyfw9s/hF/H2z+ETefvn8CLe/jncxds/h0/i7Z/Di3n75/AS3v45fDJv/xw+hbd/Di/l7Z/Dp/L2z+HTePvn8Ol8u7QesYqJbJfoEMT2Tilb9hNwi3WzevmYmjoZWFLnl8Jf22gnfEO6DqOS+1PwOf9CpNHVJncS+jyk0cUmOwk9HGl0rcknCH0W0uhSk+sIPQBpdKXJtYQ2I43DWLKF0F/NBhqrn2wk9KdIoytNLif0YaTRhSYXEPpDpNF1Jp2EfhtpdJnJYkK/jjS6yqSD0C8hjS4yaSf080ija0wKhH4WaXSJyeOnkP4r0nYiP6H/gPQQIj+hf4X0WUR+Qj+E9NlEfkLfh3QekZ/QdyE9lMhP6NuRHkbkJ/SNSH+PyE/oJqTzifyEvg7pc4j8hK5BejiRn9A/QHoEkZ/QC5EeSeQn9BykRxH5CT0D6XOJ/IS+GOnRRP6TSE9G2kHkJ/SFSI8h8hP6PKTPI/ITejjSY4n8hD4L6QIiP6EHIH0+kZ/QZqQvIPIT+qtZQI8j8hP6U6QLifyEPoz0eCI/oT9E+kIiP6HfRnoCkZ/QryN9EZGf0C8hPZHIT+jnkS4i8hP6WaQnEfn/Rdof6WIiP6H/gHQJkZ/Qv0J6MpGf0A8hPYXIT+j7kC4l8hP6LqSnEvkJfTvS04j8QC/YeABmOnI2VGUj7h1tQPLZvdCr5SsBW7q55Kg7/tq1YvxDsfXA8QWL3F2dx+c5BbFrUwsJupaPdAryCcjpM9tomFitPwRJF4sTcV4otvbkivGDN5iXbV5PfAI4gs+WbcSo1H7baLK1tH4/x7+pxwL8Yvx5cdPhK0TTTvG1nhgkfpYmfh0Si/GtNP2HLH3LZS9BfxZiQxZDSvkWEHDZ1uynATL9czP6E7H1svUVwCCdm65C3uKNx5dBafGDqZ3LkjdBEttoIRml4eKKqyqWVCyuWFQt3nZEBDezEbvCBpwOysUgpRjf7Co5IbbvkwrFjvsL1mJk1nwoJ/6+jO0lds20orOCkExn3PH3uBw+/hpzeEFsPypdhskfxJhVJPkx+ZckuYskE7sqC4gTFOOhgmZArejxACRz4+7hvfHwpZk4dFMcYkuOeuJPFqBmqtpPSFnu1CyrJy4ViFwdrvuaSXEApZgodqwpWIeRWOtnB5Ai35d/87WeKO944o8U3AlfPYkYqZnTdVcRl7WNischJ79KpdzxrpJ9Ve0paXKF7akXWnsWxyzu1FYU/1HMKp7yxE/Ij0BSd9dsUiCEpEBP/GtPAirvTlwuJqbIt32FubsErPYAMTXXamv7qRmr52LVZKqDetV5EqsLnGLrzTDZbBsNznJrZUGjKQEKauuMjXWn5ltjo9yJfmJHs/wMrgDE8ldt7UPspDbyi1+mUqg94JtH+HLUfLtyke8L+ZfAJ3asLlgudkgFdfKn4OMIKVsnorK2iokQxEFTTxRTVdbYODEBdVfl9EyuQFr+KswJGpIMpRsdae1t/JLos6QTcymc03Hp52RKWPclVcRWl5VIzaTPp9LLIhiCXUwIGBZijRbQCl45SmXNNTRzV8lRkju2hwPUucHPzPGsr4g5qnTrjoN9hQocXDYjWB33pXMp5HPZ/mVmLmK8G3WzgCiktVmGNsIuDm0sJubJJa9jusovieG4W6FXto0yYaxL8Jh6UCgn4xS7nscRFNl3fYFhpcrQb+thAoKhH7W1uUxotwEwp47KAlPF3/cCj7u8y9aG+luP9fOM73GbtqAIxSBCyQlP/JB8UQ+pR1VHJN/d+i+TrX0LqSlU4i6h4k6XkERaKeJDjEu5rO74keRuwmfhG5wYpa19xSDax3xY58Q1BXW6FgxWbmu7GFwwsfR2HFvExCUidKNs+Qai8/fl0ZBDchi67l6pE4CR+nRKS8QuAaUUu5wsfydrxS3dF3vix0ToXE5P/EN5D+S3vpPpo336YLTvBiGz8Y94oNkc2P/GYq1iozQC2tqHMtnaT0ClCtOVOgFkyYtQp6r4IU98dUG+NMZ2VadtSLpKEOazKjqoCjaJcU/B0pKjteRTZBvdRuaLbvQ80PbQUcX4YXkZaffN2JfL62Tb7fdYMO1b4vik2PFcAT6U9cRPIeMjPSotBU9wjjjRRjiJb+mi36na1PKvR7A7X10fJTH0ovg1BaJaGz/EXKGFl3oSfqvnEr9dclS1H5By3PGLCmBchdmwJ+63JgcDW29+l3ji+8XxPTgYguE9QwzTVvml29Rlu6/TE/9S3JS8zPbjTdZN4voU/Yz22Fw94GDJCCeN68WxOX/0Y8gdXMdJ4jo6iM1dQuoT/0gcD7r5RGz9oEc0bZKyxfh4GD/KD9nafsGsEFzoVqjJxxYxtVWyUV4TaZuvpOFoYoPFBMBWsYvsSYgdV1nFDtGKPbFYbD1lFuMnRWjuMtvtj+C6H8fj9hcxEcSYxC4zTTQDErwCJVklcFs3ArEKMpxhpcuITivGuMu3YOnx52Mb0HWUdV9FqufpqLMmH6Z8Pc/QAf5F6ZxnUPrjtk3W+JqCSigkQYPufglrx5WpuL39xVvLxI4nC5wAyl99lkp1j1f070k0wNAJnsyNPvs8t8Znxx6AfiP/7p/EqbGFzgtQuyOxrdCcPZ4JgYIyd+uBHvQQxVUdoSy7JzEW2zwXnAkYnBzCpOijLZ749dY5HVng0Wba0TPko2BO1sOOotmIkoOMHMO1I0fMjz5vDGbV+jWMQdeDX/oHzB6Snd9CFbZ7vo++RVFHN+SanI3IGeezIsXl82vMZzEgpL/TUaMWBgV5OEYsJVOpbgLL66EFkliJ5IgBOHFJSUZD9IF+dIi+4FMcoo9KBaSVznVnjKxJwnhMPvkJ2juONX2Nw8iNGn31EzoOLxCYk18qJgo9iWarp/ykNAqbpBDZCs9Hdgu2vNi6GVr/WEzGcXapXFSgGr9Tn+iO349+8o3jt8OTKOMyeko/I+83Z5TvSTi4jBr0Mxr2zRlZPYlCd8e1Ji4zhyozsePSd0lmLx7/hsyyCtjsRJzTlXUc4aqOa3HKdcsFqPTCOYnK4z1z45Vf9Mztqvyshzwm76r8nLyS54nv7b5gbkcWTAA80BqJvE3ueF6XuytrCxkduipfINuywDHNHd+LTKLYlbUJI3FA/0Js7TpluxPfnqgl6xV0T8WkVE8ir6eq/J9QgCcOfz+/WSL+ChcjX13hGfOpaHq+6pK8PatHialOT/nx1QcpW3eVajyAGFDJzWPT/jx+OJ3+MKR/c7VdTL3gKf98NaxzNmP6wRBy4wnM1stQS5t6IBH4e5zumGQiiCcxaJOnwwU96vluG1v/uOOVnwvu1LaSTiZP+du33CTGd4ubTkH6E6Jpt9sCHLB6In3ZbZv3imh6TexYmHInPK/2uC8Z9IX0clV7Z/PI+fE88LGb3LbHX3KbXiQFzotDgfGt3Q/N7SgtrornfaaOd7o7BllFcF2iJz7o1eQPobOvFcu7b/bhCLzpSyj/E9H0FpS/Q+i7hOe7C+Z25GEJb+qWIJESXgFZd1FZxfi7qIFKIj/D0MG2vgAD2seq8bkjbPKUv2u7u5UQ88zgzZ5lmtgtmj7FUQWqCpXcZSX1/aQqEdhjFVOvVJUXvCp1emyP768yfeCBMQ/YxLFQJ49pE4jTW6uEtMfafLY7/q+58dItIGMXCJQMgDJQJoDd8dI3QbQ9ZP/IXb7v5qs9af14mH7cibxXRdvjOz2ml0Dh2HjiWJycmbaSokJgxfFF0NCJ0lchx+YpvUVt6p6ssr/4S1XxzVi5MmD0JMhsGUwcO80gqE3pdqjKqwQC1e1A1Sn8hLmqfV/zCMj5/bldWe8oblCcE8/biz1v9FrselVcj4NcLUr9dvT2P7A7mKqKHbembPf8F/r6BHT69k5czjmQPR+dqVWaLKZEe+wiN/ZLMCNBGtbSbBVidmJUME2VJx7FAWS/GO+SJx/Br6dw9jkOZp/22BhMRqfEA1tugmTZ8qkjdGKco/CiX0pV2WPnifF/iombBcp8M2F+7QhdO7zVjeF7uOSDUX8eZcY1J/AOqmi5hTA/QnL8Qn6MMm/E51LyrUgksgunOUBNTuikDz7hXy6Qmft/ZQlCy01lgpR918yZ3edgpe4l3KAtZ/EGts5O7bRtOE7zmvIxZtwldx+hqwI7CjqGCDpCI2U+k9LRTRegdfKwkeDeOsXbtuCOxdUV11Qsq7i2wrtsMz+G29pWQcsYjOPJgEk9c7C1hfrgviqD29sH95wM7oV9cF+Wwe3qg7s4g7usD+6xGdwT+uAelsF9bh/c/SGugu1cVMXH3ZX92hSHMPPOynH5yT/DdIWbJ5FpgTJPuukwzHuOfqJi+PkxjuEHyLDmmIqhi2coR4a/qRmaP+UY8pGhVl2Hp05wDF8kgeGREyqGDTzDbmR4TM3wMs/wN2R4Rs3wxMccw/3I8HNm4787Fx2VMi10x7cmD5nolgmZRcnDQZ2lFoIkd5jIhoHCSToXLorosvhxU8Yq29Z2X0a71fXRbtUmWhnnRmw6OZHEBf8WXAg+IdCFIO4AJRplWIfk4aoSYfnJQygcJTb8N8xrn8UtePkyDiYjhJw4rFp4HjlEFqwoRvuvLXT9iMwl+5KdTGJ8uEG2j67B7SMQ9yqzIm6VWUfcXRatuH+0GIv7AMTJT30ErbEMt9ygvJeY7llN1JmfnaPNvNZsnPmV+D29xhqcbv0HDlGPFf6IeqylctY5mC+YgCBdh0NMPowE1piXfk2oKiFdccaru96SR2LJuLqSPz2Ia5rVBQ5WoqO3RMd3WeIfPqIlOuSWg9SVL0BXvoLsmPg0rfdvleT8iGo1/6Bm2WLHpXkBjq1gahnDx1sHabIPDijDx56hdEfznkPEIoilIsd8NJNnrBiJ27DpmGPyVIyZbyWGQ0BclTkATHOcjRwHLb0cCJ6CopPJU3wpx+QkgjWnqGtYMxy7e5fcNpyzJNs9a9DGFblFTHCjJutfo1TYW/JPKXtmuafogKsyaHtGb/moD4N+zdzbRXHJx3kF7fY42R5StW2Dqm1nG7XtVL22DRygjXTpP7it4WTVKc7DctzTDuDueVbBzithxQLuB/cBNhB3tobY4ASYCcUmoiBkhwDnKh3PZeH3xJNZ+yFofcVE7KF7LHqEfia2Hv4H9WYkUfxjWAvJFx2gTn0b8RTPFeCek7zngMrHWf9B90zbU7Z2unXbRvhcJalkueJssu+7CGZNcaVGg396EZtExdeQiqGqsZDj+GAIMsBl5HfWc3KIVmkBC0izPVeA81b54QNUYtyMlBv/gXO+Q/KdEDr/ZiLWdUpQfPFngo4v3iNoretPgrF1PSj0Kscd74c1Wq+MOZpnIRnWRScj6rI+66Os9wV91/z1B9TQ3tgPneqdr/Ttazdj+jMwOduOSlZUy20fgnoS9IFQVfsBW9vTOHClPAWgnMfwK875v6sWW/QBbYuL9tOWu5O9P5CcYTDkjP2AzM0vulBlZVMv/F+0snX7Daxs+oeclQ34QLVV/vL73KZKFdkld6W3oDfipqi87QP2IIxstVYRbz/IEy/DnbMsd2o2glbccWE7L2xHXXbjNg72yrb30LJS86Gh3iR76upttranM6y4w9iyum8i/ZmurbLlxHvcIJC7H/fpoMC/wRqQFvhH/KYt8PdmbYG39uGUrzNo8uL30UZSsvU96g2FhU5hwzpwic92VjkFtJ5zsUVw45gf5epR44mfkaemOFJfR0bqwHc5Uj/wHpv/vEstQvlVBc4Omv8fzQ7OY2V+9Q4dQZqVAvHREs4OoMBz04+UCt6n3NsZN3m4zB6YkumSs3e65Pwup0s3vUunS075ynfoBE0UJJHsOpASL6NfNSXOVpU4xqhEG85qnnlP36mZWMmivGcfXdzf8x6ZmZQcTdoNHOGOd6iJ/QZSJPd/mUqp3hew9kM//rkYv7SgAjcZbG1vZWH3utm+4UFYIpS8/oyZ7P8SQXugW0zPVj2SfXUfe0wmDTd4dIfPXtCtxq0wmHb3r13rvq1LwP0V5ZnPre6OrH7iZSmY5WzAF0srbJ4vyPZ4wo5zPbv8x304T+q0td0uqMqu3qcsTP5OHiMVgjXgc2M7Pg+Vc1Bf72S+EyDG3yX1SZTB/ED+BWoU3NaFZKO9IHOjfTubWNS+nUrR/UpatzJZgsyhVu3lZMKVVeBJFJNlV50MGf4PKco2793W5h6heSA2Vd676EZycOFmFTs8o1J3jbRy0rS/rTzfq3iOiDPBtuEN8ooDFI+vPBxHiTa+rfeI+0hV/BiX1cVvaxSzIUDf90DF9GA28tu6inEnLgUVXCXjyxJVHWHZfckSOWbDlx1W7CPC3r+520yfm+cThZ3FnsG+EFuKSqp4C53nAakfGVOloW37quInuydqn4eqB1lgic1AV2eB1G378MGS1da2Gx+uEKffurUn/SJMHTGa4xW2TTkwQmaB8SZo0H2VqnvV8t2LsNGge5GKbbkR27yKRE6HmKqI54LQ94whz4SOYZfCtwblG6GiyUEp1dbBJexJEmH4PjKMVzM8fZJjKEOG35xku4y3bcFuyG2CkV2Do7a2nWTqVgVj0FaBvk+gHoSuyBiEhmoGIU6opEBX6d03c4uQ7uv5cWUIa7+rSfvFFmmbytb2acYMbpvJuMT/NvErnvflv+xlEify0aPXE4/uP4MhhG8jrW8min1/Dx0Unt7NSupie8xfyAEQjm6Y/GAv7R9dFmX14chSVh+5b9GJDkFuwl0SfDFQPrSHtl5hFl1E5EMo37dXtYjYvLt3EXE1W4UhHy4ibsD3skgB7+7RFn5ntlL4vXtp4QT5KRaObznK17HC12bTwlsglIeqC5/FFT6bFY58WLg/c/ZBlPXX3XQ7+a5dYI2BzIUaYerYTaexQWS6Api6yZZPTXpVtHo0na+ixmC+2j66d75KIJg8oNaU+WpjlnbD5i8Zc7cfCYY21R2jpeawUlFVUKqNK5VAUCqqSyl1b7Zmlnyrysi+b1TabD2V3LiLzolQLGWWvBwNYsge2n7NSBwAru7L9dJfzNJjBZX027BNX9tN0+PPauRHdlFTfo6FW3bRIf9nxLSpabElGH49zSXY4xnKbu9D2VHFjFhB+PU0C9qe4Sl+1Yen6DDpm6jtTbImyh+lsrExo87Mxv4tl7LmDYPWHruLa+0Tb6jWRE+//o1roiff/HZrIjE+ky6JAmZlSfQDs86S6LKMweHsPgaHU1BK8jaDVoi/TlrhvhGqPvfTEWfY5/6dVsh53aDPPPwG12caX1e1Qslr39gKRW/8m60wyKS0gtmk0woHM/rb/xj3t+RvBeZVlbXpsVe5tWnTa2xtevBrZW2672udtekfMsps6aOPh/XU/ZOddNUQeRXVbinGdenxBU6h+yI97nrGXUG51atY9F1LX9MfXIpZQiskTOK7uLbRQsWSarH1SL47fsqduJa8ujeBzBPOz3h17w/s1d+XXsHV8ywHnV1em99Xmp+wNA/QNPksjb2vNG0sTQ1NQyfdiXMxyXkkycj0ovSendRZTyesOfR1qy35V1dcq3qyKS3ubQ1PQVYC/nW7VQxX8gyDgGFQt0vFMI9nyAOGvO4Z3HTzAO4kd5QWyDugJsndp1Rz0a9JpFRglR/H2CPq2CEpGmuX78VYM5D8/L13/bgA2qgqcTkxyUfp/ky+rf3nRDuj3YmIVSzvllZWPIeK7C5T1f7sTPm5bj+O1PxsKL175FpPYgK+OHUeeXFqpPLilKf8UOxP+L7Uju3U5oimN0OR78Z2QPHYOFZsiT9tZ+vf7XyLWLnZtuZ9zcVogLcdaSETnFNkSZePBotP5NJvm3ftgFLLf0ZAaRDM4JEdWnnZZrHjmgIrmc4h30aQYYMNZ3LjGfLwDrIMpFNgtJxKWA6S7e3VWdaElFWIG9tWFD0f2U9tp488QJb3cDf7Wki+ta3gBihuHMWhakjhcTWCfMUOZZIb20F2BtiC+NIC+cAOuicMqsVpxFTIuOToBvwV67N4xAdif9lB56aJ7N8NdZD3naBqg/97qOLnPVlW3GmxUw+PL5udpntfbSL+BoMM996MW4rjttNNHDv17bjFsWUHe1ldfmg77VS/otXrXkbqePpbtd9Y+u9fJpvEtjZzis6xlkKJyc9PEX9ULca/Ts/Wb7LK/yIvAr5/dXLsdt34d2i8nLWd8U14CTtQ2r60/I8x/jdfZvxfv9gn/2rG/4jC/zLyp9nXLpAvhJLloS9j7SoFAbprPFWxxB0/UbHYHd9VscjTcb7T5hAWix0TRQirPeMPwpp+00kL/gJO/nwb3RE5t/f9nMOe+IlKyCOV9w50MRP06thh0oeWKZ1oM1fff25mv6VjP53D34FPCgRXTopKgfqwUB9e6QvVBxyheinY5As5aiNNjlAkvKJwvOOGeqnOgecAOEqKLx4n8KcyXHwxHpIQCQMV80uOcCwUcoQjkoPkJTgGaJijsRr4KrgnzXdEGqEYPELAAf+TX+4HHLX1oaDQNEGYBaFjDLKEST3wsBZIL8yMxEKB8DiJxSBX7+//5pVM9s72zJ9R4fF653lLyhpXSXWRcL1/Kp6JEC0pXuILxYIuPDHDdTr8U6olXziAx1awJH3zl7uUIxFcp1efKTNAoXyi4+z35ssXOFW/S0//TpfRxSx+7QKnbrzA8CcM4nfOZ/lr4vuu73T3fE53pyHfNFd4ZX1TJNwQDEualOr6OK/Ur48Sb2fxLVc6dc+rU/SAcxry+2cWas9NSv++9Uo1v31e3/zHNfk7NfymEZZLVrPfqN/5QiqFz2is0PWbYVY/HkJ8NJcProY8EDoMnRg92wnAIbyzJ5XCH4zg73COQ9gMU618SPcghPjLkW34MygIeyBcDmEZ+Ji1ED4K4V52OECecj7kjQsFU7PdNGJQP+taUz97HvuddxwcB//7ZH1++ptq5F+/JZVqwXE71z4rN3+ObeAN1hbhiuGXXDil4Dz+XErLjQs8JId+FjzKyaLkU6r8PhtkL4b+mXXpYqdQkWufkZs/I9cxI7dwRm5xRW7Z7NyW7NZ+a3I6su/Ousdyh5mkuwZ/dy6nUg8PgnQ7l+in68xVpctL10ctz0hWV/HzVOp+HIRn5NorcvMrc4tbLXebaT3xd/PboC1eIweeZZRVketUFUU+KFsW5Nf4RSqFv7fIevQqpZ4VuY7ZuessrVl3AzfW62f4O3Fo21Es/1Yz1f+TaD+An6/Bt+PvvnXwA2jnOvi/0Oa2plJjGK6cq3kA6rcO+IMClfsesys3/26LK9fRkeXKLVyTLeYW35Ej5pa19qvKdYZQUpC3kMgOGgBZrCT/i9AGIR+zpk+kLPe0CpY7LBPYmQcm3A+7jhHDkPiEnVbwIYpeb6JHKRRjzCQzPbfhVizgcjM99OFHSOxkMceQ+NJMc1uIaa6wUGIFErdbaJrVQJges1BNtCFhzqJsf0K27wFxr3KwxqPZtIP6oBqmF7Npderxz3s59HiMHyOxsD/NrQOJ6/vTcm7Gn2zDUEZOxbgJY8aBoq9VKtoOxEPKgRyj8+iP2r/AmIN5NGvCdhj+7FXYns+nZ06Y8NfQX+XTg0ECSJTDn6DC9vOR9GiNUlTizlEsjYOpdZ5ZdUJsyvLGbYJlJyHeVhrqbdYmEfwZO75XiDLg22KCxIiTSPzeRM+cQAUK/zTRNDYk8NeiVqU+dnYknROn6+dl03MM5iAxL5s73EQ5aXMGxvyCsXUi8TIQTyu53d6fSjcc/1gHUmId/v79LPiTMKVtbadgmUdOelUKwC+NGIXEJv78jjfYISU/x9Tvs5Mofm1ivLkm4T+f/3z+8/nP5z+f/18/xSPpvHwBO8fdPlI9rzcZhLuz1fR+DX2S0crZVY9+j+arnFn1GVsXnKOcz8TOEVfOYFLOpFLOcJJZvDKfVs7c+vxUKkLO5zE70+eGkXVOf2f63DQ64aW0cvbWMyxCOXNLOUNqqEY/lt6Duth5dex8pWz1+kA5G0w5o6rlLKcKbx7iVNXbyhTVX1P+qRSVZ6+d8qcYrdTjOKPn2J3/q3aSPsde8/mItesJFubk03AYCy9g4TQWzmLhEhbWsnAlC+9g4QMs/C0Ln2LhVhbuZuFHLDzBwhy2zhzGwgtYOI2Fs1i4hIW1LFzJwjtY+AALf8vCp1i4lYW7WfgRC0+wMIed0zuMhRewcBoLZ7FwCQtrWbiShXew8AEW/paFT7FwKwt3s/AjFp5gYQ7rx8NYeAELp7Fw1gh9u5k9c+bFjsLFNbGwFHOUFpUVlU6cHCNUyS0lpUXFpUWl4ykuMCZ/yBde4VgZbIrittSUoqlFxRNLaZLJt0hNsai0arKjUPKtiE5a6PK4Kqpd3ilTiyfV4rGa4x2FuEMWwN0sj2dJFU0+XhCKoqsaJF8NhFITDeuUb/VhKdjUKBSFI1KwqGKGeyJkzagV4VhRTaw+FJhYHxAIVeeL1glFgVVhyI+GUhONYRVWEV6IawqGfMjIvjWGJCyyHv5KwWb4C/Wuh7hIwCf5hKJgnbe2ydcQ9NYFmnopyNTvZ0eaeiVyfDLJw+travKtonko36/zN5GK+Rrq/ZAuIpE/tFxaRk00KhT5Iw24J/Rv998RzDcr/qv3Hg1B5Ve1fl/5jNWcsdh7TwU7h07Dn6WhSzTpJZZe4vYJ+kqP6/QT4PuU9Iq/f5ABAYZna8aH9P4b8/VmzXigONa1bDzIYbJbNX55CWM1a8aXtf3V44mR/q5lvlxJr/jvOWygW6Opv+a6EOF6NjYotDI+7GXp1wm99bfoyH8j06lZMx41D1GPR1r9KfK3adIr41vLWerxMJuN+dr0dwu9d6vw84FHv6ce543aP65Jv5Ol38nSt1jU/HZNeL8mvTLfWcAmHL+aop9e+TykSa/MXz6bpx7Hjeq/TtP/BLavTC6AwH03S9/lP6pJ33vfC6VXf0P5T2nSb2Ppty0UVP1QMOg/nZr0uE1JQxZv7rv819mer0Uz31Puk9HKqy0fX6K0cemV+aC8TJ9fSx9m9U/Po1j646eZ/hjXt/j5kHLfj6KYHE16Ra4eTfnKub493r7LV8KTmvTKfFRgwU5T3+lzTOr0O9n5kTt9p6f/QWwDTEmvnD+8n6W3auxXOx4MYeUXa3Al/R0G448SDhHU5/gqn9oa5j9MfftfVd/jPs7rmT2xQ3PxgMS5Ov6rv0H5hTfS8E173+X39bEAtzIeq3FzepxV45b0+KnGs9LjohrP7h3vVHhOehxT4/101xcW0MpeXbx/ejxR4wPS44QaH5j2/2p8UNqvq/HBaX+txnPTfliN23r9qwq3p/2mGh+S9odq/Ky0n1PjZ6f9lxrPS/slNT407W/U+DDddZUFVpGKf1Dj+b39XoWfk+7Parz3nhQ1PiIDMxGf/UlKi9MzdjP1cAXD8bET/7mS4fiYh//4Sf/rbUflbOPVpOzhwkHNfSt/ZPzK80PlrOJ3GK48t1RwfF6IuPLcUTmbuZLhxW6K388KCDPcrsn/pwzfOYfiryn+n+FrL6X4w2xj434zxZ+Yy/Y3mJPZaKZyHdDI9QrBbennpOl1P8PXavASC8V3avAAw5XnvAr+EMPXafCtDH9Ck89nSv6svyhnLRdkUVx5vq6ckXwVwwUNfhfDlefTylnInQxXnksrZ0UfYbjyfF555jo8m+KOhWr+OQzv1ORzM8OPa/DfZ+vb85OEP7M/bsqm7bhO42d2M3ynBk8yXLtflsqm7f6Bpt1zc/B7pn+YmsPsU5NPBeHP9DNGci0n/EOEMk0/DefoyysY9PcbCX+mn6Hro7Mz6v9Lhmvr+STJJ9O//T0H5waZ/mqbwX1Shwzws/shPlg4zvqvMraPZfgPNe11YT/9e6Pq++nnf7cB/lQ//XvHXjDA3zLI56gBPsCqj19C8MzxrsKAv9YAv9EA7zDAHzPA9xrgXxrgZ/fXxy81wFcAfp55sNDI5FX2aW/pr38P1yaDfN7sr38/15f99dtr6ACca/bOH5R1TMEA/fxnGuCLDfDbDfAHBujX54kBODfP7C9/N8gnOUD/HrTcgfr80wfq31O2bKD+fW0tyG8+J2NescYg/8cG6t93ttmAfz/Lf68m/6MG/KZBtL+3MDsJKuuFQfr84UH6982tMeD/8yDkyZxHPWvAv2uQ/r11Awbr819ogM83wBsN8HsH69vPbwfr33+33SCf/Qb4+FwDv2SAV+dSvckBtd6WGvA/bID/JVf/XrxuA/4hNv17/Zw2ff5rbbR/ads3aNO/d+8Og3zeMcCPGeAD7Qb3JBrgFXb9ewmvNuCXDPCfGOB/MMBftNP+tZzNT4qZQl8huM46blJTJCJNalzlk/yRQLBpUmNTpCYUbIhO8tX4S0qLJ7km4fVSk4v8jY3keil+t7w4AynJQKYK6fcoo7Ear9vbm533B0ZvWZaUeL34gECqD3u9ntJ5kTC91e20X4KtLKbXdp3JW6rfKs3k00hTiu/ynhan8h7qN1UlJtWHQN5ona8pGPA2BWvd1dK0lUG/FGlyz6su9tLcyK121T539VSvy+VSKjD3dHROqjy9NhbGLMvwDeVQfTjoD7nnLOzNnzC5MOtF/lC0qY+cXOksoo3ICjULuKbXRppu8DUF3Iu8rtpGUsXG+dXl3r4q2SuYf2WIXfvoKfN66yPk2Q9eIXgmb0qfBr/2TebTSaJ5ufo0kui8T/zNqXrfWv5m3nK1CNVnqKXqM9dS9Zlrqfpbaan6DLRUfUZaWnKGWlpy5lpacrqV9zdJUSlWW1uEl//NmbnQ63FXL/J6hd4LYr1Sg9ePF8FGBR3I6w1EvCtCkRpfyBuATh31+mLNgj/S0BgKSsFA0bTyssn6TN7ex6BeUHzTKoE+Sg3EGhpWQRKO8vY+PWWsXu+shRVVLq9rXiVec0tqzr4zqefPmlXtWuRdVDHD40IOVRYBNUDuOxS8ld+fV1Hlningc1cF09696XTytxj2fVephpfereiPxojkQrqEM7y2U1sD3RttM6qpe+euiquo/LRuDyY3VGZmz92DqaOiPq71VdehpERg2tG/S1OdN721kmHsMkpyFaYayrjVUhPd5+WlWmkyrgHVtnLvVZuZxRhcuZvZpIbX42aUhq9fQJuHQt70ZcLf7vJgdc7k/lAdATIvF9bUqM/bped7ye+mvLFoMJB5qbCmBk3BYEYF+rr6V52cXn2qyaCP6621nd7wBms9886421XXTehdUK3Tk3Sun9Vy6dxorDUMEE/xiBn3OWfaG7kGOBPmLqjW5h+IRrx1MNKC8ui9s7p9Dr0dm0J9hxdpZ/gtzZ3PWkEyb0vWSlMTjXKNn74wPEPvp3WLsNPJ3YibefexrsPIuAg5MxP1ZdF6uahvYlfnoHt/u8G15xovSy4M1vEF3+76b00vD0ZqtZaTviRdLQEZtr/dFdyaMskvJ7UCnf4N2DojsM619EY92+B2cb325K4n16iCvBqmd694ptl8B/dn64yBOtKlL6/XxKkurYY4dpm09k76TK0q14vrTGboBeE6ldDenp5pyo2relu+pDTzEm7tFKM+LFAX9n8BK6yodPyKAAA='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np

def solve(P):
    N = P.shape[0]
    top = np.empty(N, dtype=np.int64)
    second = np.empty(N, dtype=np.int64)
    count = np.empty(N, dtype=np.int64)
    sum = np.empty(N + 1, dtype=np.int64)

    sum[N] = 0
    p = N - 1
    top[p] = P[N - 1]
    second[p] = 0
    count[p] = 1
    sum[p] = 0
    ans = 0
    for j in range(N - 2, -1, -1):
        x = P[j]
        pt = N #始めて1番目でなくなる位置
        for i in range(p, N):
            if x < top[i]:
                pt = i
                break
        ps = N
        for i in range(pt, N):
            if x < second[i]:
                ps = i
                break
        asum = sum[ps]
        ccount = 0
        psum = ps - 1
        for i in range(ps - 1, pt, -1):
            ccount += count[i]
            if top[i - 1] != top[i]:
                second[psum] = x
                asum += x * ccount
                sum[psum] = asum
                count[psum] = ccount
                ccount = 0
                psum -= 1
        if pt < ps:
            ccount += count[pt]
            second[psum] = x
            asum += x * ccount
            sum[psum] = asum
            count[psum] = ccount
            ccount = 0
            psum -= 1
        for i in range(pt - 1, p, -1):
            ccount += count[i]
            if top[i - 1] != top[i]:
                asum += top[i] * ccount
                sum[psum] = asum
                second[psum] = top[i]
                top[psum] = x
                count[psum] = ccount
                ccount = 0
                psum -= 1
        if p < pt:
            ccount += count[p]
            asum += top[p] * ccount
            sum[psum] = asum
            second[psum] = top[p]
            top[psum] = x
            count[psum] = ccount
            psum -= 1

        top[psum] = x
        second[psum] = 0
        sum[psum] = asum
        count[psum] = 1
        ans += asum
        p = psum
    return ans


def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    P = np.empty(N, dtype=np.int64)
    i = 0
    for s in stdin.readline().split():
        P[i] = int(s)
        i += 1
    ans = solve(P)
    print(ans)
'''

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    def search(self, val):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)  # 一番上の長さ

        while step:
            if i + step <= self.size and s + self.tree[i + step] < val:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

def sol():
    N = int(input())
    P = [None] + list(map(int, input().split()))

    pToI = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    ans = 0
    for p in range(1, N + 1)[:: -1]:
        i = pToI[p]
        left = tree.sum(i)  # 左にある個数
        tree.add(i)
        right = (N - p) - left  # 右にある個数(処理済みの内，左にないものの個数)

        # L1 < L2 < p < R1 < R2
        L1 = tree.search(left - 1) if left >= 2 else 0
        L2 = tree.search(left) if left >= 1 else 0
        R1 = tree.search(left + 2) if right >= 1 else N + 1
        R2 = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if L2 != 0:
            cnt += (L2 - L1) * (R1 - i)
        if R1 != 0:
            cnt += (R2 - R1) * (i - L2)

        ans += cnt * p

    print(ans)

sol()

Submission status: Accepted

Solution code:
N, *P = map(int, open(0).read().split())

idx_dict = [0] * (N + 1)
for i in range(N):
    idx_dict[P[i]] = i + 1

cnt = 0
l = [0] + [i for i in range(N + 1)]
r = [i + 1 for i in range((N + 1))] + [N + 1]

for v in range(1, N + 1):
    i = idx_dict[v]
    
    l1 = l[i]
    l2 = l[l1]
    r1 = r[i]
    r2 = r[r1]
    cnt += ((l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1)) * v
    
    l[r1] = l1
    r[l1] = r1
    
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
lst = list(enumerate(list(map(int, input().split()))))

sorted_lst = sorted(lst, key = lambda x: x[1])
left_next_index = list(range(-1, n - 1)) + [-1, -1]
right_next_index = list(range(1, n + 1)) + [n, n]

ans = 0
for i, p in sorted_lst:
    l2 = left_next_index[i]
    l1 = left_next_index[l2]
    r1 = right_next_index[i]
    r2 = right_next_index[r1]
    
    a = p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
    ans += a
    
    left_next_index[r1] = l2
    right_next_index[l2] = r1
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = nl()
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
    
ans = 0
l = [0] + [i for i in range(n+1)]
r = [i+1 for i in range(n+1)] + [n+1]

for i in range(1,n+1):
    v = q[i]
    l1,r1 = l[v],r[v]
    l2,r2 = l[l1],r[r1]
    ans += i*((v-l1)*(r2-r1) + (r1-v)*(l1-l2))
    l[r1] = l1
    r[l1] = r1
  
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter


def solve(n, ppp):
    qqq = sorted(enumerate(ppp), key=itemgetter(1))
    left_next_index = list(range(-1, n - 1)) + [-1, -1]
    right_next_index = list(range(1, n + 1)) + [n, n]
    ans = 0
    for i, p in qqq:
        l2 = left_next_index[i]
        l1 = left_next_index[l2]
        r1 = right_next_index[i]
        r2 = right_next_index[r1]
        ans += p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
        left_next_index[r1] = l2
        right_next_index[l2] = r1
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Accepted

Solution code:
import bisect
def find_left(P,position):
    N=len(P)
    left1=[-1]*N
    left2=[-1]*N
    stack=[]
    popped=[[] for i in range(len(P))]
    stack=[P[0]]
    for i in range(1,len(P)):
        while stack:
            if stack[-1]<P[i]:
                
                popped[i]+=[stack.pop()]
            else:
                left1[i]=stack[-1]
                stack+=[P[i]]
                
                break
                
        if stack==[]:
            stack+=[P[i]]
            left1[i]=-1
        if left1[i]==-1:
            left2[i]==-1
        else:
            val=left1[i]
            pos=position[val]
            big_val_pos=len(popped[pos])
            if popped[pos]:
                big_val_pos=bisect.bisect_left(popped[pos],P[i])
                if big_val_pos<len(popped[pos]):
                    left2[i]=popped[pos][big_val_pos]
            #for x in popped[pos]:
            #    if x>P[i]:
            #        left2[i]=x
            #        break
                    
            
            
            if left2[i]==-1:
                if len(stack)>=3:
                    left2[i]=stack[-3]
    #print(popped)
    return left1,left2


def find_right(P,position):
    position=[len(P)-x-1 for x in position]
    right1,right2=find_left(P[::-1],position)
    return right1[::-1],right2[::-1]
input()
P=list(map(int,input().strip().split(" ")))



N=len(P)
P=[p-1 for p in P]
position=[0]*len(P)
for i in range(len(P)):
    position[P[i]]=i

left1,left2=find_left(P,position)
right1,right2=find_right(P,position)

for i in range(N):
    if left1[i]!=-1:
        left1[i]=position[left1[i]]
    if left2[i]!=-1:
        left2[i]=position[left2[i]]
    
    if right1[i]==-1:
        right1[i]=N
    else:
        right1[i]=position[right1[i]]
    
    if right2[i]==-1:
        right2[i]=N
    else:
        right2[i]=position[right2[i]]
        
#print(P)
#print(left1,left2)
#print(right1,right2)

ans=0
for i in range(N):
    L1,L2,R1,R2=left1[i],left2[i],right1[i],right2[i]
    val=P[i]+1
    if val==N:
        
        continue
    temp=0
    if L1==-1:
        temp+=(i+1)*(R2-R1)
    elif R1==N:
        temp+=(L1-L2)*(N-i)
    else:
        temp+=(L1-L2)*(R1-i)
        temp+=(i-L1)*(R2-R1)
    
    ans+=temp*val
    
print(ans)