Đỉnh của dãy Bitonic

General
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Một dãy số nguyên $a_1, a_2, \dots, a_N$ ($N \ge 3$) được gọi là dãy Bitonic nếu tồn tại một chỉ số đỉnh $p$ ($2 \le p \le N - 1$) sao cho $a_1 < a_2 < \dots < a_p$ và $a_p > a_{p+1} > \dots > a_N$. Hãy tìm giá trị tại đỉnh $a_p$ và vị trí $p$ bằng thuật toán $O(\log N)$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra
  • Một dòng gồm hai số nguyên: $a_p$ và $p$.
Ví dụ
Input Output
6\n1 4 9 12 7 2 12 4
Giới hạn
  • $3 \le N \le 2 \cdot 10^5$
  • $|a_i| \le 10^9$
Draft saved