```python
class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be greater than zero")
        self.capacity = capacity
        self.cache = {}
        self.order = []

    def get(self, key: int) -> int:
        if key in self.cache:
            # Move the accessed key to the end of the order list
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update the existing key and move it to the end of the order list
            self.cache[key] = value
            self.order.remove(key)
            self.order.append(key)
        else:
            # Add a new key-value pair
            self.cache[key] = value
            self.order.append(key)

            # If the cache exceeds capacity, remove the least recently used key
            if len(self.cache) > self.capacity:
                lru_key = self.order.pop(0)
                del self.cache[lru_key]
```