fork download
copy 
  1. n = int(input())
  2. a = list(map(int, input().split()))
  3.  
  4. #premin[i] = min_id(a[:i+1])
  5. #premax[i] = max_id(a[:i+1])
  6. #postmin[i] = min_id(a[i:])
  7. #postmax[i] = max_id(a[i:])
  8.  
  9. premin = [0]
  10. premax = [0]
  11. for i in range(1, n):
  12.     lastmin = premin[-1]
  13.     premin.append(lastmin if a[lastmin] < a[i] else i)
  14.  
  15.     lastmax = premax[-1]
  16.     premax.append(lastmax if a[lastmax] > a[i] else i)
  17.  
  18. #считаем перевернутые postmin и postmax
  19. postmin = [n-1]
  20. postmax = [n-1]
  21. for i in range(n-2, -1, -1):
  22.     lastmin = postmin[-1]
  23.     postmin.append(lastmin if a[lastmin] < a[i] else i)
  24.  
  25.     lastmax = postmax[-1]
  26.     postmax.append(lastmax if a[lastmax] > a[i] else i)
  27.  
  28. postmin = postmin[::-1]
  29. postmax = postmax[::-1]
  30.  
  31. print('postmin', *postmin)
  32. print('postmax', *postmax)
  33. print('premin', *premin)
  34. print('premax', *premax)
  35.  
  36. #i_1, j_1
  37. ib, jb = None, None
  38. res = float('inf')
  39. for x in range(1, n):
  40. 	i = premin[x-1]
  41. 	j = postmax[x]
  42. 	if a[i] - a[j] < res:
  43. 		res = a[i] - a[j]
  44. 		ib, jb = i, j
  45. print(ib+1, jb+1)
  46.  
  47. #i_2, j_2
  48. ib, jb = None, None
  49. res = float('-inf')
  50. for x in range(1, n):
  51. 	i = premax[x-1]
  52. 	j = postmin[x]
  53. 	if a[i] - a[j] > res:
  54. 		res = a[i] - a[j]
  55. 		ib, jb = i, j
  56. print(ib+1, jb+1)
Success #stdin #stdout 0.09s 14096KB
comments (?)
stdin
copy 
6
0 1 0 3 0 3
stdout
copy 
postmin 0 2 2 4 4 5
postmax 3 3 3 3 5 5
premin 0 0 2 2 4 4
premax 0 1 1 3 3 5
1 4
4 5
https://ideone.com/nIX5c1
language:
Python 3 (python  3.12)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!