• Source 
    1. #include <iostream>
    2. #include <stack>
    3. using namespace std;
    4.  
    5. struct data
    6. {
    7. 	long long height;
    8. 	int check_behind;
    9. 	long the_same;
    10. } typedef data;
    11.  
    12. data info (long long h, int behind, long same)
    13. {
    14. 	data tmp;
    15. 	tmp.height = h;
    16. 	tmp.check_behind=behind;
    17. 	tmp.the_same=same;
    18. 	return tmp;
    19. }
    20.  
    21. int main ()
    22. {
    23. 	stack <data> S;
    24.  
    25. 	long n;
    26. 	cin>>n;
    27. 	long count=0;
    28. 	for (long i=1; i<=n; i++)
    29. 	{
    30. 		long long h;
    31. 		cin>>h;
    32. 		data TOP;
    33. 		if (!S.empty()) TOP = S.top();
    34. 		if (S.empty())
    35. 		{
    36. 			S.push(info (h, 0, 0));
    37. 		}
    38. 		else if (!S.empty() && TOP.height>h)
    39. 		{
    40. 			S.push(info (h, 1, 0));
    41. 			count++;
    42. 		}
    43. 		else if (!S.empty() && TOP.height==h)
    44. 		{
    45. 			count++;
    46. 			count+=TOP.the_same;
    47. 			if (TOP.check_behind==1)
    48. 			{
    49. 				count++;
    50. 			}
    51. 			S.push(info(h, TOP.check_behind, TOP.the_same+1));
    52. 		}
    53. 		else if (!S.empty() && TOP.height<h)
    54. 		{
    55. 			while (TOP.height<h)
    56. 			{
    57. 				count++;
    58. 				S.pop();
    59. 				if (S.empty()) break;
    60. 				TOP = S.top();
    61. 			}
    62. 			if (!S.empty()) TOP = S.top();
    63. 			if (!S.empty() && TOP.height==h)
    64. 			{
    65. 				count++;
    66. 				count+=TOP.the_same;
    67. 				if (TOP.check_behind==1)
    68. 				{
    69. 					count++;
    70. 				}
    71. 				S.push(info(h, TOP.check_behind, TOP.the_same+1));
    72. 			}
    73. 			else if (!S.empty() && TOP.height>h)
    74. 			{
    75. 				count++;
    76. 				S.push(info(h, 1, 0));
    77. 			}
    78. 			else S.push(info(h, 0, 0));
    79. 		}
    80. 	}
    81. 	cout<<count;
    82. 	return 0;
    83. }