1 #include <cstdio>

 2 #include <cstring>

 3 #include <iostream>

 4 #include <algorithm>

 5 #include <vector>

 6 #include <cmath>

 7

 8 using namespace std;

 9 #define ll long long

10 #define Min(a,b) ((a)>(b)?(b):(a))

11 #define Max(a,b) ((a)>(b)?(a):(b))

12 const int MAXN = 5e4 + 13;

13 int N, a[MAXN], STmax[MAXN][30], STmin[MAXN][30];

14 int Logn[MAXN];

15

16 void pre_log()

17 {

18     Logn[1] = 0, Logn[2] = 1;

19     for(int i = 3; i <= MAXN; i++) {

20         Logn[i] = Logn[i/2] + 1;

21     }

22 }

23

24 void pre_st()

25 {

26     for(int i = 1; i <= N; i++) STmax[i][0] = i, STmin[i][0] = i;

27     int k = Logn[N];

28     for(int j = 1; j <= k; j++) {

29         for(int i = 1; i + (1<<j) - 1 <= N; i++) {

30             if(a[STmin[i][j-1]] < a[STmin[i+(1<<(j-1))][j-1]]) STmin[i][j] = STmin[i][j-1];

31             else STmin[i][j] = STmin[i+(1<<(j-1))][j-1];

32             if(a[STmax[i][j-1]] > a[STmax[i+(1<<(j-1))][j-1]]) STmax[i][j] = STmax[i][j-1];

33             else STmax[i][j] = STmax[i+(1<<(j-1))][j-1];

34         }

35     }

36 }

37

38 int query_min(int l, int r)

39 {

40     // int k = log(1.0*(r - l + 1))/log(2.0);

41     int k = Logn[r - l + 1];

42     if(a[STmin[l][k]] > a[STmin[r-(1<<k)+1][k]])  return STmin[r-(1<<k)+1][k];

43     else return STmin[l][k];

44 }

45

46 int query_max(int l, int r)

47 {

48     int k = log(1.0*(r - l + 1))/log(2.0);

49     if(a[STmax[l][k]] < a[STmax[r-(1<<k)+1][k]])  return STmax[r-(1<<k)+1][k];

50     else return STmax[l][k];

51 }

52

53 int query(int l, int r)

54 {

55     int p = l;

56     while(l < r) {

57         int mid = (l+r+1)>>1;

58         if(query_min(p, mid) == p)  l = mid;

59         else r = mid-1;

60     }

61     return l;

62 }

63

64 int main()

65 {

66     pre_log();

67     while(scanf("%d", &N) != EOF) {

68         for(int i = 1; i <= N; i++) {

69             scanf("%d", &a[i]);

70         }

71         pre_st();

72         int ans = -1;

73         for(int i = 1; i < N; i++) {

74             //先以i为最小值进行查找最大的管辖范围

75             //再求范围内的最大j

76             int j = query_max(i, query(i, N));

77             if(j - i == 0)

78                 continue;

79             else

80                 ans = Max(ans, j - i);

81         }

82         printf("%d\n", ans);

83     }

84     return 0;

85 }